Rotate List
Rotate List is a medium linked list problem solved with the dummy node pattern pattern.
The best approach, optimal (make a ring, then cut), runs in O(n) time and O(1) space.
Below are 2 approaches in Java, from brute force (rotate one step k times) up.
Problem
Rotate a linked list to the right by k places: the last k nodes move to the front, keeping their order.
Examples
Example 1
- Input
head = [1, 2, 3, 4, 5], k = 2- Output
[4, 5, 1, 2, 3]
Example 2
- Input
head = [0, 1, 2], k = 4- Output
[2, 0, 1]- Why
- Rotating by 4 is the same as rotating by 4 % 3 = 1.
Constraints
- The list has
0to500nodes. 0 <= k <= 2 * 10^9
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Brute force (rotate one step k times) | O(n · k) | O(1) |
| Optimal (make a ring, then cut) | O(n) | O(1) |
1Brute force (rotate one step k times)
O(n · k)Each single rotation walks the list; k < n after the modulo.O(1)Move the last node to the front, k % n times.
- Compute n; k %= n.
- Repeat k times: find the second-to-last node, detach the last and put it first.
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
int n = 0;
for (ListNode p = head; p != null; p = p.next) n++;
k %= n;
for (int r = 0; r < k; r++) {
ListNode prev = head;
while (prev.next.next != null) prev = prev.next;
ListNode last = prev.next;
prev.next = null;
last.next = head;
head = last;
}
return head;
}
}2Optimal (make a ring, then cut)
O(n)O(1)Find the length n and the tail, and link the tail to the head. The new tail is n - k % n steps from the old head. Cut after it.
- Walk to the tail, counting n; tail.next = head.
- Move n - k % n - 1 steps from head to reach the new tail.
- newHead = newTail.next; newTail.next = null.
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if (head == null || head.next == null) return head;
int n = 1;
ListNode tail = head;
while (tail.next != null) { tail = tail.next; n++; }
tail.next = head;
ListNode newTail = head;
for (int i = 0; i < n - k % n - 1; i++) newTail = newTail.next;
ListNode newHead = newTail.next;
newTail.next = null;
return newHead;
}
}Edge cases to test
- Empty or single-node list
- k is a multiple of the length
- k much larger than the length
Hints
Hint 1
Join the tail to the head to make a ring. Where should you cut it?
FAQ
What is the best time complexity for Rotate List?
Optimal (make a ring, then cut) runs in O(n) time and O(1) extra space.
Which pattern does Rotate List use?
It is a linked list problem that uses the dummy node pattern pattern. Other problems with the same pattern: Remove Linked List Elements, Delete Nodes From Linked List Present in Array, Merge Two Sorted Lists.
Is there a brute force solution for Rotate List?
Yes. Brute force (rotate one step k times) takes O(n · k) time and O(1) space. Move the last node to the front, k % n times.
Which edge cases should I test for Rotate List?
Empty or single-node list; k is a multiple of the length; k much larger than the length.