Rotate List
Close the list into a ring through the tail, then cut it n - k mod n steps in.
Decision · step 4 of 6Rewiring 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.
What you will see
The list becomes a ring, then is cut at the new head.
Cost
| Best | O(n) |
|---|---|
| Average | O(n) |
| Worst | O(n) |
| Space | O(1) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Each node announces its value and what it points to; each step announces the pointer change ("node 3 now points to node 5").
Reduced motion: Pointer arrows redraw in place with a brief emphasis instead of animating the detach and reattach.
Before this
Related
Taught by the same lesson
Rewiring a List covers these too, in the same run.