Rotate List
Rotate a linked list to the right by k places in one pass plus a walk: count the nodes, reduce k modulo n, close the list into a ring and cut it at the new tail.
Problem Understanding
Rotate List: given the head of a linked list, rotate it to the right by k places. Rotating right by one moves the last node to the front.
Examples: [1,2,3,4,5], k = 2 → [4,5,1,2,3]; [0,1,2], k = 4 → [2,0,1].
The Intuition: Only Two Links Change
After the rotation, the last k nodes come first, in the same order, followed by the first n - k nodes. So:
- Count the nodes, keeping the tail. Reduce
ktok % n; if it is 0, nothing moves. - Make a ring: the old tail now points to the old head.
- Find the new tail: it is the (n − k)-th node, n − k − 1 steps from head.
- Cut: the new head is the node after it, and its next becomes null.
Same idea as Rotate Array, but on a list only links change. Finding a node a fixed distance from the end also shows up in Remove Nth Node From End of List.
Interactive Walkthrough
ROTATE RIGHT BY k
head
#0
→
#1
→
#2
→ NULL
n
:
k
4
walk n−k−1
:
Rotate right by k = 4: the last k nodes move to the front
Next
tail starts at head #0 (0), n = 1
head
k
Legend & Complexity
tail while counting, newTail while finding the cut
The new head, right after the cut
The rotated list
↺ back to #0: the tail linked to the head, a ring
Time
O(n)
Space
O(1)
Watch the row end change to ↺ back to #0 when the ring closes, and the row start at the new head after the cut. Try Big k to see the modulo at work.
Dry Run Table
Input: [1,2,3,4,5], k = 2.
| Step | What happens |
|---|---|
| Count | tail = 5, n = 5 |
| Modulo | k = 2 % 5 = 2 |
| Ring | 5 → 1 |
| Walk | n − k − 1 = 2 steps: newTail = 3 |
| Cut | newHead = 4; 3 → null |
Answer: [4,5,1,2,3].
The Solution Template
Count, modulo, ring, walk, cut.
Rotate List Code
1var rotateRight = function(head, k) {2 if (!head || !head.next || k === 0) return head;3 let tail = head, n = 1;4 while (tail.next) { tail = tail.next; n++; }5 k %= n;6 if (k === 0) return head;7 tail.next = head;8 let newTail = head;9 for (let i = 0; i < n - k - 1; i++) newTail = newTail.next;10 const newHead = newTail.next;11 newTail.next = null;12 return newHead;13};
Edge Cases & Common Mistakes
- k ≥ n: always reduce with
k % nfirst. - k % n = 0: return head before making the ring, or remember to break it.
- Empty list or one node: return head; there is nothing to rotate (and n would be 0 in the modulo).
- Off by one: the new tail is n − k − 1 steps from head, not n − k.
- Rotating left instead: right by k is left by n − k.
Summary
Count n and keep the tail, reduce k to k % n, link the tail to the head, walk n − k − 1 steps to the new tail, and cut after it. O(n) time, O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet