Rotate the list
Move the last k nodes to the front by closing the chain into a ring, then cutting it at the right place. About 14 minutes.
Make it a ring
Rotating right by k moves the last k nodes to the front. In 1, 2, 3, 4, 5 with k equal to 2, the last two nodes, 4 and 5, go in front to give 4, 5, 1, 2, 3.
The trick: connect the last node back to the head to make a ring. A ring has no start, so the rotation is just a choice of where to cut it. The new tail is the node k places before the old end.
tail.next = head # the end meets the front
Walk to the end. The list has 7 nodes and the tail is node 7. k mod 7 is 3.
Reduce k first
Rotating by the list length changes nothing, so use k modulo n. If the remainder is 0, return the list as it is.
Count the nodes on the way to finding the tail, so one walk gives you both n and the tail. An empty list or a one-node list is returned straight away, since division by n would otherwise fail.
k %= n
if k == 0:
return headA list has 5 nodes and k is 12. How much do you rotate?
- ABy 2, since 12 mod 5 is 2
- BBy 12, one place at a time
- CNot at all
Show the answer
By 2, since 12 mod 5 is 2. After every 5 places the list returns to its start, so only the remainder matters.
Rotate list
Given the head of a singly linked list and a non-negative integer k, rotate the list to the right by k places, so the last k nodes move to the front, and return the new head. If k is larger than the length, keep going around.
head = [1, 2, 3, 4, 5], k = 2 → [4, 5, 1, 2, 3]
0 ≤ number of nodes ≤ 5,000 · 0 ≤ k ≤ 2,000,000,000