We need to rotate the linked list to the right by k
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL
Explanation:
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL
We can see that It is no different from partitioning the linked list into two group and swap the group’s position.
-
We iterate through the linked list to find the end.
-
Point the end of the linked list to the head
-
We record the length of linked list
-
If shifting is not a multiple of length, (k % len != 0), we will find the end of first group by progress from tail (len – (k % len)) nodes.
5.then the new head will be tail -> next
Potential bugs
Length of linked list
Since we are not using dummy head, the linked list starts with length 1.
ListNode* rotateRight(ListNode* head, int k) {
if (!head)
return head;
ListNode *newH, *newTail;
newH = newTail = head;
int length = 1;
//first figure the length with n
while(newTail -> next){
newTail = newTail -> next;
length ++;
}
//point end of second group to head
newTail -> next = head;
//find the end of first group, first group len is len - k
//can skip if rotation doesn't change linked list
if (k % length){
for (int i = 0; i < length - (k % length); i ++){
newTail = newTail -> next;
}
}
newH = newTail -> next;
newTail -> next = NULL;
return newH;
}