Well, in the case of a linked list instead of an array, the problem becomes easier. We just need to find the node that will be the new head of the list after the rotation and then restructure the list.
1 class Solution { 2 public: 3 ListNode* rotateRight(ListNode* head, int k) { 4 if (!head) return NULL; 5 int len = listLength(head); 6 k %= len; 7 ListNode* fast = head; 8 for (int i = 0; i < k; i++) 9 fast = fast -> next; 10 ListNode* slow = head; 11 while (fast -> next) { 12 slow = slow -> next; 13 fast = fast -> next; 14 } 15 fast -> next = head; 16 head = slow -> next; 17 slow -> next = NULL; 18 return head; 19 } 20 private: 21 int listLength(ListNode* head) { 22 int len = 0; 23 while (head) { 24 len++; 25 head = head -> next; 26 } 27 return len; 28 } 29 };
