61. 旋转链表

链表常用方法之——快慢指针法

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head==NULL||k==0)
            return head;
        ListNode *left=head;
        ListNode *right=head;
        ListNode *cur=head;
        int n=0;
        while(cur)
        {
            n++;
            cur=cur->next;
        }
        k=k%n;
        for (int i=1;i<=k;i++)
            right=right->next;
        if (!right)
            return head;
        while(right->next)
        {
            left=left->next;
            right=right->next;
        }
        right->next=head;
        right=left->next;
        left->next=NULL;
        return right;
    }
};

另一个种方法
先遍历整个链表获得链表长度n，然后此时把链表头和尾链接起来，再往后走n - k % n个节点就到达新链表的头结点前一个点，这时断开链表即可。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head||k==0)
            return head;
        ListNode *cur=head;
        int n=1;
        while(cur->next)//找到最后一个位置
        {
            n++;
            cur=cur->next;
        }
        cur->next=head;//首尾相连
        k=n-k%n;
        for(int i=0;i<k;i++)
            cur=cur->next;
        ListNode* newhead=cur->next;
        cur->next=NULL;
        return newhead;
    }
};