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, Python, C++ and JavaScript, 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
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
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 code in Java, Python, C++ and JavaScript.
| 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;
}
}class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next:
return head
n = 0
p = head
while p:
n += 1
p = p.next
k %= n
for _ in range(k):
prev = head
while prev.next.next:
prev = prev.next
last = prev.next
prev.next = None
last.next = head
head = last
return headclass Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr) return head;
int n = 0;
for (ListNode* p = head; p != nullptr; p = p->next) n++;
k %= n;
for (int r = 0; r < k; r++) {
ListNode* prev = head;
while (prev->next->next != nullptr) prev = prev->next;
ListNode* last = prev->next;
prev->next = nullptr;
last->next = head;
head = last;
}
return head;
}
};function rotateRight(head, k) {
if (head === null || head.next === null) return head;
let n = 0;
for (let p = head; p !== null; p = p.next) n++;
k %= n;
for (let r = 0; r < k; r++) {
let prev = head;
while (prev.next.next !== null) prev = prev.next;
const 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;
}
}class Solution:
def rotateRight(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
if not head or not head.next:
return head
n = 1
tail = head
while tail.next:
tail = tail.next
n += 1
tail.next = head
newTail = head
for _ in range(n - k % n - 1):
newTail = newTail.next
newHead = newTail.next
newTail.next = None
return newHeadclass Solution {
public:
ListNode* rotateRight(ListNode* head, int k) {
if (head == nullptr || head->next == nullptr) return head;
int n = 1;
ListNode* tail = head;
while (tail->next != nullptr) { 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 = nullptr;
return newHead;
}
};function rotateRight(head, k) {
if (head === null || head.next === null) return head;
let n = 1;
let tail = head;
while (tail.next !== null) { tail = tail.next; n++; }
tail.next = head;
let newTail = head;
for (let i = 0; i < n - k % n - 1; i++) newTail = newTail.next;
const 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.