AlgoMaster Logo

Rotate List

Last Updated: March 29, 2026

medium
3 min read

Understanding the Problem

At first, "rotate right by k places" might sound like you need to move nodes one at a time, k times. But that would be painfully slow when k is in the billions. So the first thing to notice is that rotating a list of length n by n places gives you back the original list. That means only k % n rotations actually matter.

The second key observation: rotating right by k is the same as taking the last k nodes and moving them to the front. If the list is [1, 2, 3, 4, 5] and k=2, you split it into [1, 2, 3] and [4, 5], then stitch them back as [4, 5, 1, 2, 3]. So the problem boils down to finding the right split point, breaking the list there, and reconnecting the pieces.

Key Constraints:

  • 0 <= number of nodes <= 500 → The list can be empty. We need to handle the null head case.
  • -100 <= Node.val <= 100 → Node values don't affect the approach. This is purely a structural manipulation problem.
  • 0 <= k <= 2 * 10^9 → k can be massive, far larger than the list length. We absolutely cannot iterate k times. We must reduce k using modulo.

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

Intuition

The most direct interpretation: rotate right by 1 means taking the last node and moving it to the front. So do that k times. Each rotation requires traversing to the second-to-last node, detaching the tail, and prepending it to the head.

This works correctly, but when k is 2 billion and the list has 5 nodes, we are doing 2 billion traversals. We need to be smarter.

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 entire list to find the tail, and we detach one node at a time when we could move a whole block at once. What if we figured out exactly where to split the list in a single pass?

Approach 2: Find Split Point (Optimal)

Intuition

Here's the key insight: rotating right by k is just splitting the list at the right place and swapping the two halves. If the list is [1, 2, 3, 4, 5] and k=2, the split point is after node 3. The tail portion [4, 5] becomes the new front, and the head portion [1, 2, 3] follows.

To find the split point: if the list has n nodes and the effective rotation is k % n, the new tail is the node at position n - k - 1 (0-indexed from the head). The node after it becomes the new head. To do this efficiently, we can connect the tail to the head to form a circular list, then walk to the new tail position and break the circle there.

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