61. Rotate List.md

61. Rotate List

思路

题目要求循环移位链表k步。
不要被题目迷惑了，这题根本不需要移位，只需要在倒数第k个位置处将链表截断然后将后半部分接到最前面就可以了。现在问题就是怎样快速找到倒数第k个的位置。
涉及到链表倒数某个位置的一般就是用一个双指针pre和p，初始都为head，先让p后移k步再让pre和p同时后移，这样当p到达链尾时pre就处于倒数第k个位置。
注意k可能大于链表的长度，所以要先将k对链表长度len取模。
时间复杂度O(n)，空间复杂度O(1)

C++

/**
 * 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) return head;
        int len = 0;
        ListNode *p = head, *pre=head, *res;
        while(p){
            len++;
            p = p -> next;
        } // 获得链表长度
        k %= len;
        if(k == 0) return head; 
        p = head;
        while(k--) p = p -> next; // p先后移k步
        while(p -> next){ // pre和p同时后移直到p -> next为NULL
            p = p -> next;
            pre = pre -> next;
        } // 此时pre -> next 就是倒数第k个元素
        res = pre -> next;
        pre -> next = NULL;
        p -> next = head;
        return res;
    }
};