Rotate List

You are given the head of a singly linked list and a non-negative integer k.

Rotate the list to the right by k places. One rotation step takes the last node off the end and puts it in front of the head. Return the head of the list after all k steps.

Lists are written as arrays of values, e.g. [1,2,3]; an empty list is []. Note that k can be far larger than the length of the list.

Example 1

Example 2

Example 3

Constraints

• 0 <= number of nodes <= 500
• -100 <= Node.val <= 100
• 0 <= k <= 2 * 109

Pattern Path · Linked Lists · problem 77 of 169

Start simple

Perform k single-step rotations, each walking to the second-to-last node: O(n·k) time, hopeless when k is around two billion.

The key idea

A right rotation by k moves the last k nodes, in order, to the front. Since rotating by the list length n changes nothing, only k mod n matters; this is what makes huge k values cheap.

With s = k mod n, the new head is the node at index n - s, and the new tail is the node just before it, at index n - s - 1. So the work is:

1. Walk the list once to get n and the current tail.
2. If s is 0 the list is unchanged. Otherwise link the old tail to the old head, turning the list into a ring.
3. Walk n - s - 1 steps from the head to the new tail, take its next as the new head, and cut the ring there.

Closing the ring first means you never need to stitch two separate pieces together; a single cut produces the rotated list. Two linear walks give O(n) time and O(1) extra space.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def rotateRight(self, head, k):
        if head is None:
            return None

        # Measure the length and find the current tail.
        length, tail = 1, head
        while tail.next:
            tail = tail.next
            length += 1

        shift = k % length
        if shift == 0:
            return head

        # Close the ring, then cut it right after the new tail.
        tail.next = head
        new_tail = head
        for _ in range(length - shift - 1):
            new_tail = new_tail.next
        new_head = new_tail.next
        new_tail.next = None
        return new_head

JavaScript

var rotateRight = function(head, k) {
  if (!head) return null;

  // Measure the length and find the current tail.
  let length = 1, tail = head;
  while (tail.next) {
    tail = tail.next;
    length++;
  }

  const shift = k % length;
  if (shift === 0) return head;

  // Close the ring, then cut it right after the new tail.
  tail.next = head;
  let newTail = head;
  for (let i = 0; i < length - shift - 1; i++) newTail = newTail.next;
  const newHead = newTail.next;
  newTail.next = null;
  return newHead;
};

What the interviewer is checking

It checks whether you spot the modulo reduction before writing a loop over k, and whether you handle empty lists, single nodes and k that is a multiple of the length without special-case spaghetti.

Mistakes to avoid

• Looping k times without reducing k modulo the length, which times out for large k.
• Taking k mod n before checking for an empty list (division by zero).
• Forgetting to cut the ring, which returns a cyclic list.
• Off-by-one when walking to the new tail (it is at index n - s - 1, not n - s).

Follow-ups to expect

• How would you rotate left by k instead? (New tail at index s - 1.)
• How would you rotate an array in place? (Three reversals.)
• What if the list were doubly linked? (Walk backward from tail.)

In real software

Circular buffers and round-robin schedulers rotate their starting point exactly this way, and reducing an offset modulo the size is how ring buffers map ever-growing counters onto fixed slots.

Practice next