Rotate List
Rotate a linked list to the right by k places.
- The number of nodes in the list is in the range [0, 500].
- -100 <= Node.val <= 100
- 0 <= k <= 2 * 10⁹
Intuition
Rotate list shifts a linked list right by k places. Thinking of it as moving nodes one at a time, k times, is both slow and unnecessary — a rotation is really just one cut in a different place.
Rotating right by k means the last k nodes move to the front. So the list is being split at a single point and the two pieces swapped. There is no shuffling to do; the only question is where the new break belongs.
Two preliminaries make it simple. First, k can exceed the list length, and rotating by exactly n returns the original list — so reduce k modulo n immediately. Forgetting this is the usual cause of a timeout on large k, since the naive loop would run millions of times to no effect.
Second, joining the tail to the head to form a ring removes all the edge cases. Once the list is circular there is no end to fall off, and the whole operation becomes: walk to the new tail and cut there.
- The new tail sits n − k − 1 steps from the original head, and the new head is the node right after it.
Cut by setting that node's next to null, and return the node that followed. One pass to measure the length, one partial pass to reach the cut point.
Rotation is really "cut the list at a new place". Closing it into a ring first means you never juggle two loose ends — you just walk to the new tail and break there. Whenever a rotation problem gives you a linear structure, ask whether making it circular removes the special cases; it usually does.
Approach
Before reading on: price up what the direct approach costs here, then ask which pointers must be saved before you overwrite anything. Aim for O(n) time and O(1) space.
Measure the list and normalise k
Walk once to count n and reach the last node. Then set k %= n. Without the modulo, a large k loops pointlessly — and rotating by a multiple of n is a no-op, so if k becomes 0, return the list unchanged.
Handle the trivial cases first
An empty list or a single node is its own rotation regardless of k. Returning early keeps the arithmetic below free of guards that would otherwise clutter it.
Close the list into a ring
Point the old tail's next at the head. This is what removes the edge cases — with no end to run off, the rotation is purely a matter of choosing where to break the circle.
Walk to the new tail
From the original head, step n - k - 1 times. That node is the last one in the rotated order, since the final k nodes are the ones moving to the front.
Cut and return
The new head is the new tail's next. Set that next to null to open the ring, then return the new head. Cutting before saving the new head loses the reference to the rest of the list — order matters in these two lines.
Cost of the rotation
One full pass to measure plus a partial pass to the cut point gives O(n) time and O(1) space. The work is independent of k after the modulo, which is what makes a k of one billion no slower than a k of one.
Solution & live demo
Common pitfalls
Not reducing k modulo the length
for _ in range(k):
# rotate one stepk %= n if k == 0: return head
k can far exceed the list length — rotating a 3-node list 2,000,000 times is the same as rotating it twice. Without the modulo the loop runs k times, timing out on the exact inputs the problem is testing.
Counting the length off by one
n, tail = 0, head
while tail.next:
tail = tail.next; n += 1n, tail = 1, head
while tail.next:
tail = tail.next; n += 1The loop advances once per edge, not per node, so starting at 0 undercounts by one. That makes k % n wrong and the cut lands one position off.
Walking n - k steps to find the new tail
for _ in range(n - k):
new_tail = new_tail.nextfor _ in range(n - k - 1):
new_tail = new_tail.nextStarting from head, taking n - k steps lands on the new head, one past the node you need to cut after. The new tail sits at index n - k - 1.
Edge cases
k %= n reduces both to the trivial case — return head unchanged.
Early return; nothing to rotate.