Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

http://www.lintcode.com/en/problem/rotate-list/

Discussion

• 先将队尾和head连起来组成个环，这样list length n也就知道了。
• 再从head移动n-k次，断开，返回rotated list head就可以了。
• 因为k有可能大于n，所以是移动n-k%n次，有在这里犯错。

Solution

class Solution {
public:
    /**
     * @param head: the list
     * @param k: rotate to the right k places
     * @return: the list after rotation
     */
    ListNode *rotateRight(ListNode *head, int k) {
        // write your code here
        if(head ==  NULL) return NULL;
        int len = 1;
        ListNode *cur = head;
        while(cur->next != NULL) {
            cur = cur->next;
            len++;
        }
        cur->next = head;
        for(int i=0; i<len-k%len; i++) {
            cur = cur->next;
        }
        ListNode *result = cur->next;
        cur->next = NULL;
        return result;
    }
};