visual walkthrough
Rotate List
Make a ring, then cut it at the right place.
The idea
Rotating right by k moves the last k nodes to the front. Rotating by the length n changes nothing, so only k mod n matters.
Join the tail to the head to make a ring, then cut it in the right place: the node n − k from the start becomes the new tail.
Complexity
| approach | time | space |
|---|---|---|
| One step at a time | O(n × k) | O(1) |
| Ring and cut | O(n) | O(1) |