Rotate List
Problem
head of a singly linked list and a non-negative integer
k. Shift the whole list to the right by k places: each step, the last
node becomes the new head. Return the head of the rotated list.head=[1,2,3,4,5], k=2Output[4,5,1,2,3]head=[0,1,2], k=4Output[2,0,1]0 ≤ n ≤ 500 · -100 ≤ Node.val ≤ 100 · 0 ≤ k ≤ 2·109
Try it yourself
class Solution {
public ListNode rotateRight(ListNode head, int k) {
}
}
n changes nothing, so only k % n matters. The
answer is just the last k % n nodes moved to the front: link the tail to the head to
form a ring, then cut it right after node n - k%n.Instinct Nodes joined by next pointers and the task is to reverse, splice, merge, reorder or remove in place - grab a dummy head and rewire pointers carefully.
Memory hack Save next, flip, step - never let go of a rope before you've grabbed the next one.
Open the Linked List Techniques guide →Approaches
Brute ForceRotate One Step at a Time
O(n · min(k, n))Space O(1)Simulate the definition: one right-rotation = detach the last node and put it
in front. Doing it k times is hopeless for k = 2·109,
so at least reduce to k % n steps; each step still walks the list to find
the second-to-last node.
public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null) return head; int n = 0; for (ListNode c = head; c != null; c = c.next) n++; k %= n; for (int step = 0; step < k; step++) { ListNode prev = head; while (prev.next.next != null) prev = prev.next; // second-to-last ListNode last = prev.next; prev.next = null; last.next = head; head = last; } return head; }
Direct simulation; quadratic in the worst case (k % n close to n).
BetterNode Array & Relink
O(n)Space O(n)Store the nodes in an ArrayList so any position is O(1) away. After
rotation the new head is node n - k; walk the indices circularly from
there and relink next pointers, terminating the last one with
null.
public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null) return head; List<ListNode> nodes = new ArrayList<>(); for (ListNode c = head; c != null; c = c.next) nodes.add(c); int n = nodes.size(); k %= n; if (k == 0) return head; int start = n - k; // index of the new head for (int i = 0; i < n - 1; i++) { nodes.get((start + i) % n).next = nodes.get((start + i + 1) % n); } nodes.get((start + n - 1) % n).next = null; return nodes.get(start); }
Linear time, but the array costs O(n) extra memory.
OptimalClose the Ring, Cut at n − k
O(n)Space O(1)One pass finds the length and the tail. Linking tail.next = head
makes a ring; walking n - k%n steps from the tail lands on the
new tail. Its next is the new head — cut there.
public ListNode rotateRight(ListNode head, int k) { if (head == null || head.next == null || k == 0) return head; ListNode tail = head; int length = 1; while (tail.next != null) { tail = tail.next; length++; } tail.next = head; // make it a ring int steps = length - k % length; ListNode newTail = tail; while (steps-- > 0) newTail = newTail.next; ListNode newHead = newTail.next; newTail.next = null; // break the ring return newHead; }
Dry runhead=[1,2,3,4,5], k=2
- len12345tlength=5, ring 5→1
- steps12345tsteps = 5 - 2%5 = 3
- walk123t4h5tail moves 3 → node 3
- cut4h5123t3.next=null ✔
Two linear walks, no extra memory — the standard answer.
k % length == 0 the walk goes a full circle back to the old tail, so the
original list is returned — no special case needed.At a glance
| Level | Approach | Time | Space |
|---|---|---|---|
| Brute Force | Rotate One Step at a Time | O(n · min(k, n)) | O(1) |
| Better | Node Array & Relink | O(n) | O(n) |
| Optimal | Close the Ring, Cut at n − k | O(n) | O(1) |
- Not reducing
kmodulon— times out for huge k. - Forgetting to break the ring — returns a cyclic list (infinite loop in callers).
- Off-by-one: the new head is node
n-k(0-indexed), the new tail isn-k-1.
- Ask about
k > nand the empty list up front. - Explain that a right rotation by k = moving the last k nodes to the front.
- Mention the ring trick generalises to rotating arrays by reversals.