Question：

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

.

Anwser 1：

merge a


circle

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        assert(k >= 0);
        
        if(head == NULL) return NULL;
        
        ListNode *ret = head;
        int len = 1;
        while(ret->next != NULL){
            len++;
            ret = ret->next;
        }
        
        ret->next = head;   // merge a circle list
        
        k = k % len;
        int step = len - k - 1;     // 1 is a head note
        ret = head;
        while(step > 0){
            ret = ret->next;
            step--;
        }
        
        head = ret->next;
        ret->next = NULL;
        
        return head;
    }
};

Anwser 2：

left + right

/**
 * 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) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        assert(k >= 0);
        
        if(head == NULL) return NULL;
        
        ListNode *ret = head;
        int len = 1;
        while(ret->next != NULL){
            len++;
            ret = ret->next;
        }
        
        
        ListNode *tmp = head;
        
        k = k % len;
        int step = len - k - 1;     // 1 is a head note
        while(step > 0){
            tmp = tmp->next;        // left
            step--;
        }
        
        ListNode *tmp2 = tmp;       // right
        while(tmp2->next != NULL){
            tmp2 = tmp2->next;
        }
        
        tmp2->next = head;      // right->next
        
        ret = tmp->next;        // ret head
        tmp->next = NULL;       // left->next
        
        return ret;
    }
};