Rotate List

The problem. Given the head of a linked list, rotate it to the right by k places: the last k nodes move, in order, to the front. Return the new head. k can be much larger than the length of the list.

Example

[1, 2, 3, 4, 5], k = 2   ->  [4, 5, 1, 2, 3]
[0, 1, 2], k = 4         ->  [2, 0, 1]      (4 mod 3 = 1)
[1, 2, 3], k = 3         ->  [1, 2, 3]      (a full turn)

The idea: a rotation is a ring cut in a different place

Rotating by k doesn't change which node follows which — only where the list starts and ends. If you join the tail back to the head, the list becomes a circular list, and every rotation of it is the same ring cut open at a different point. So: count the nodes, close the ring, walk to the node that should be the new tail, and cut.

Two details make it work for any k. Rotating by n (the length) changes nothing, so only k mod n matters — that's what keeps a k of two billion fast. And the new tail is the node n − k − 1 steps from the old head, because the last k nodes come before it.

1. Brute force: rotate by one, k mod n times

1function rotateRight(head, k) {2  if (head === null || head.next === null) return head;3  let n = 0;4  for (let curr = head; curr !== null; curr = curr.next) n++;5  for (let r = 0; r < k % n; r++) {          // rotate by one, k mod n times6    let beforeTail = head;7    while (beforeTail.next.next !== null) beforeTail = beforeTail.next;8    const tail = beforeTail.next;9    beforeTail.next = null;                  // detach the last node...10    tail.next = head;                        // ...and put it in front11    head = tail;12  }13  return head;14}

Time O(n · (k mod n)) — up to O(n²), space O(1). Each single rotation walks the whole list to find the node before the tail. Without the k % n, a huge k would never finish.

2. Close the ring, then cut it

1function rotateRight(head, k) {2  if (head === null || head.next === null) return head;3  let n = 1, tail = head;4  while (tail.next !== null) {         // count the nodes and find the tail5    tail = tail.next;6    n++;7  }8  k %= n;                              // rotating by n changes nothing9  if (k === 0) return head;10  tail.next = head;                    // close the list into a ring11  let newTail = head;12  for (let i = 0; i < n - k - 1; i++) newTail = newTail.next;   // n - k - 1 steps from the head13  const newHead = newTail.next;14  newTail.next = null;                 // cut the ring after the new tail15  return newHead;16}

Time O(n), space O(1). One full walk to count and find the tail, then at most one more partial walk to the cut. Making the list circular for a moment turns move k nodes from the back to the front into choose where the ring opens.

Comparing the approaches

Edge cases to test

Variations