Rotate List
Rotate a linked list to the right by k places, which means the last k nodes move to the front and everything else slides along behind them. The function takes a plain array of values and the number k, builds the list inside, and returns a plain array. Instead of moving nodes one at a time, join the tail back to the head to make a ring , then cut the ring open at the right place. Because rotating by the full length changes nothing, k is first reduced with a remainder.
Constraints
- The number of nodes is between 0 and 500
- -100 ≤ node value ≤ 100
- 0 ≤ k ≤ 2 × 109
- k can be far larger than the number of nodes
Example
Input
values = [1, 2, 3, 4, 5], k = 2Output
[4, 5, 1, 2, 3]Explanation The last two nodes, 4 and 5, move to the front, and 1, 2, 3 follow them.
In plain terms
- Rotate right
- Shift every node k places towards the back; nodes that fall off the end reappear at the front. Rotating [1, 2, 3] by 1 gives [3, 1, 2].
- Tail
- The last node of the list — the one whose next pointer aims at nothing.
- Remainder (k % length)
- What is left of k after removing whole loops around the list. Rotating a 5-node list by 7 lands in the same place as rotating it by 2.
- Ring
- A list whose tail points back at the head, so there is no end. It is a temporary shape here: the ring is cut open again before returning.
Each cell is one node in its original position, head first
n11
n22
n33
n44
n55
Statusinit
The list is 1 -> 2 -> 3 -> 4 -> 5 and it must rotate right by 2.
What happens in this step
list = 1 -> 2 -> 3 -> 4 -> 5 k = 2 The last two nodes should end up at the front, giving 4 -> 5 -> 1 -> 2 -> 3.
Step 1 of 6
Steps to visualize
- The cells stay where they are; what changes is where the list starts and ends.
- First walk to the tail to learn the length of the list.
- Reduce k with a remainder, because whole loops around the list change nothing.
- Count to the new tail: the node that will become the last one.
- Cut there, then join the old tail to the old head, and the node after the cut becomes the new head.
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
n11
n22
n33
n44
n55
Statusinit
The list is 1 -> 2 -> 3 -> 4 -> 5 and it must rotate right by 2.
What happens in this step
list = 1 -> 2 -> 3 -> 4 -> 5 k = 2 The last two nodes should end up at the front, giving 4 -> 5 -> 1 -> 2 -> 3.
Step 1 of 6
Solution
class ListNode {
constructor(val, next = null) {
this.val = val;
this.next = next;
}
}
function toList(values) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) {
head = new ListNode(values[i], head);
}
return head;
}
function toArray(head) {
const out = [];
for (let node = head; node !== null; node = node.next) {
out.push(node.val);
}
return out;
}
function rotateRight(values, k) {
const head = toList(values);
if (head === null || head.next === null || k === 0) {
return toArray(head);
}
let length = 1;
let tail = head;
while (tail.next !== null) {
tail = tail.next;
length++;
}
const shift = k % length;
if (shift === 0) {
return toArray(head);
}
let newTail = head;
for (let i = 1; i < length - shift; i++) {
newTail = newTail.next;
}
const newHead = newTail.next;
newTail.next = null;
tail.next = head;
return toArray(newHead);
}- Time
- O(n)
- Space
- O(n)
Test cases
| Input | Expected | Covers |
|---|---|---|
values = [1, 2, 3, 4, 5], k = 2 | [4, 5, 1, 2, 3] | example from the description |
values = [0, 1, 2], k = 4 | [2, 0, 1] | k is larger than the list, so the remainder matters |
values = [], k = 3 | [] | empty list, nothing to rotate |
values = [7], k = 99 | [7] | one node always rotates onto itself |
values = [1, 2, 3], k = 3 | [1, 2, 3] | rotating by exactly the length changes nothing |
values = [-1, 0, 4, 8, 2, 5, 7], k = 10 | [2, 5, 7, -1, 0, 4, 8] | a longer list with negative values and k above the length |