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.

Solution: Notice that k can be larger than the list size (k % list_size).
This solution traverses the list twice at most.

 1 /**
 2  * Definition for singly-linked list.
 3  * struct ListNode {
 4  *     int val;
 5  *     ListNode *next;
 6  *     ListNode(int x) : val(x), next(NULL) {}
 7  * };
 8  */
 9 class Solution {
10 public:
11     ListNode *rotateRight(ListNode *head, int k) {
12         if(!head) return NULL;
13         ListNode* tail = head;
14         int counter = 1;
15         while(tail->next) {
16             tail = tail->next;
17             counter++;
18         }
19         k = k % counter; // in case the list rotates more than one round
20         if(k == 0) return head;
21         
22         ListNode* cur = head;
23         for(int i = 0; i < counter - k - 1; i++) 
24             cur = cur->next;
25         
26         ListNode* newHead = cur->next;
27         cur->next = NULL;
28         tail->next = head;
29         
30         return newHead;
31     }
32 };