61. Rotate List

This can be solved in O(n) running time. The idea is straightforward, i.e. move to the starting point where the list rotates, connect the end to the head and return the starting point.

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 == NULL || head->next == NULL) return head;  
13:      int n = countList(head);  
14:      int r = k % n;  
15:      if (r == 0) return head;  
16:      int m = n - r;  
17:      ListNode *cur = head, *start = NULL, *end = NULL;  
18:      while (--m) {  
19:        cur = cur->next;  
20:      }  
21:      end = cur;  
22:      start = cur->next;  
23:      while (cur->next) {  
24:        cur = cur->next;  
25:      }  
26:      cur->next = head;  
27:      end->next = NULL;  
28:      return start;  
29:    }  
30:    int countList(ListNode *head) {  
31:      int count = 0;  
32:      while (head) {  
33:        count++;  
34:        head = head->next;  
35:      }  
36:      return count;  
37:    }  
38:  };