Rotate the Chain Right
MediumLinked List
Problem
A circular-buffer display shows the nodes of a singly linked list from head to tail. Each tick, the last node moves to the front.
Given the head and a number of ticks k, return the head of the list after k ticks. k can be far larger than the list.
Example 1
- Input:
- head = [1, 2, 3, 4, 5], k = 2
- Output:
- [4, 5, 1, 2, 3]
After one tick: [5, 1, 2, 3, 4]; after two: [4, 5, 1, 2, 3].
Example 2
- Input:
- head = [0, 1, 2], k = 4
- Output:
- [2, 0, 1]
Three ticks bring the list back to the start, so 4 ticks act like 1.
Constraints
- 0 ≤ number of nodes ≤ 500
- -100 ≤ node.val ≤ 100
- 0 ≤ k ≤ 2 · 10^9
Hint
Show the first hint
Simulating k ticks one by one is far too slow for k = 2 · 10^9. What happens after n ticks?
Walkthrough
How to approach it
01Clarify before coding
- Can k exceed the length? Yes, by a lot: up to 2 · 10^9.
- What about an empty list? Return it as is; the rotation is undefined but harmless.
- Should I relink nodes rather than move values? Yes.
02Brute force
Perform k ticks: each one walks to the second-to-last node and moves the tail to the front.
Cost: O(n · k) time, about 10^12 operations at the limits: hopeless.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.