Leetcode 61: rotate list

Given a list, rotate the list to the right by k places, where k is non-negative.
For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

这个题目如果找到需要rotate的节点然后变换指针就可以，注意一个点是k的取值，k可能会 超过长度，对于这种k进行的处理是，先对list求出长度，然后用k对长度取余，就是进行rotate的位置。这个题目可以先用slow fast指针找到需要rotate的节点， 再直接进行rotate指针变换。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        //sanity check
        if (head == NULL) return NULL;
        ListNode* p = head;
        int len = 0;
        while (p) {
            p = p->next;
            len++;
        }
        int k1 = k % len;
        if (k1  == 0) return head;
        ListNode* slow = head;
        ListNode* fast = head;
        for (int i = 0; i < k1-1; i++) {
            fast = fast->next;
        }
        ListNode* pre = slow;
        while (fast->next) {
            fast = fast->next;
            pre = slow;
            slow = slow->next;
        }
        pre->next = NULL;
        fast->next = head;
        head = slow;
        return head;
    }
};

updated:

这个题目有更巧的思路：
当第一遍扫描求长度的时候，最后fast->next = head， form a loop, 也是符合rotate的性质，再将fast移动len - k 位，最后进行操作，这种方法只用到了1个辅助指针。

class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == NULL || k == 0) return head;
        ListNode* fast = head;
        int count = 1;
        while(fast->next) {
            fast = fast->next;
            count++;
        }
        k = k % count;
        if (k == 0) return head;
        fast->next = head;
        int step = count - k;
        while (step > 0) {
            fast = fast->next;
            step--;
        }
        head = fast->next;
        fast->next = NULL;
        return head;
    }
};