Rotate List
Close the list into a ring through the tail, then cut it n - k mod n steps in.
Rewiring a List: Rotate right by 2
Walk n - k mod n - 1 = 5 - 2 - 1 = 2 steps from the head to 3: it becomes the new tail, and the node after it, 4, the new head.
Cost
- Best
- O(n)
- Average
- O(n)
- Worst
- O(n)
- Space
- O(1)
Before this
Related
Taught by the same lesson
Rewiring a List covers these too, in the same run.