AlgoMaster Logo

Rotate List

mediumFrequency5 min readUpdated June 23, 2026

Understanding the Problem

Rotating right by k places means moving the last node to the front, repeated k times. Done literally, that is k passes over the list, which is too slow when k reaches 2 billion. Two facts cut the work down.

First, rotating a list of length n by exactly n places returns the original list. Every full cycle of n rotations is a no-op, so only k % n rotations change anything. With n at most 500 and k up to 2 billion, reducing k by modulo is what makes the problem tractable.

Second, rotating right by k % n is the same as taking the last k % n nodes and moving them to the front as a block. For [1, 2, 3, 4, 5] and k=2, split into [1, 2, 3] and [4, 5], then reconnect as [4, 5, 1, 2, 3]. The work reduces to finding the split point, breaking the list there, and reconnecting the two pieces.

Key Constraints:

  • 0 <= number of nodes <= 500 → The list can be empty, so the null head case needs handling. The small upper bound also means an O(n) or even O(n^2) length-bound solution runs instantly; the size pressure comes from k, not n.
  • -100 <= Node.val <= 100 → Values do not affect the approach. This is a structural manipulation problem, not a value-based one.
  • 0 <= k <= 2 * 10^9 → k can be far larger than the list length, so iterating k times is out. Reducing k with k % n is required. Note that 2 billion fits in a signed 32-bit int (max about 2.147 billion), so a plain int for k is safe in Java, C++, C#, and Go.

Approach 1: Brute Force (Rotate One at a Time)

Intuition

Rotate right by 1 means detaching the last node and prepending it to the head. Repeating this k times produces a rotation by k. Each step traverses to the second-to-last node, detaches the tail, and links it in front of the current head.

The one optimization that keeps this from timing out is reducing k to k % n first. Without it, k=2 billion on a 5-node list is 2 billion traversals. Even after the reduction, each of the remaining rotations re-walks the list to find the tail, which is the weakness the next approach removes.

Algorithm

  1. If the list is empty or has one node, return it as-is.
  2. Reduce k to k % n where n is the list length (to avoid redundant full rotations).
  3. For each of the remaining k rotations:
    • Traverse to the second-to-last node.
    • Detach the last node.
    • Set the last node's next to the current head.
    • Update head to be the detached node.
  4. Return the new head.

Example Walkthrough

1Initial list, k=2 (after modulo: k=2%5=2)
head
1
2
3
4
5
null
1/6

Code

Each rotation re-traverses the list to find the tail and moves a single node, when the whole tail block could move at once. The next approach locates the split point directly and reconnects in a single pass.

Approach 2: Find Split Point (Optimal)

Intuition

A rotation by k is a single split followed by reconnecting the two halves in the opposite order. For [1, 2, 3, 4, 5] and k=2, the split falls after node 3: the tail portion [4, 5] becomes the new front and [1, 2, 3] follows. Finding that split point takes one extra walk, not k walks.

After reducing the rotation to k = k % n, the new tail is the node at position n - k - 1 (0-indexed from the head), and the node right after it becomes the new head. Connecting the original tail back to the head first turns the list into a circle, so the same single walk that locates the new tail also defines where to break the circle. The break sets the new tail's next to null, and the node past the break is returned as the new head.

Algorithm

  1. If the list is empty or has one node, or k is 0, return as-is.
  2. Traverse the list to find its length n and its tail node.
  3. Compute the effective rotation: k = k % n. If k is 0, no rotation needed.
  4. Connect the tail to the head, forming a circular list.
  5. The new tail is at position n - k - 1 from the original head. Traverse there.
  6. The new head is the node after the new tail.
  7. Break the circle by setting the new tail's next to null.
  8. Return the new head.

Example Walkthrough

1Initial list. Count length: n=5, find tail=node(5)
head
1
2
3
4
5
tail
null
1/5

Code