Generated by Codex with GPT-5

Quick facts

• Difficulty: MEDIUM
• Problem: Rotate List
• Main tags: Linked List, Two Pointers
• Frequency in source list: 25.6

What the problem is really asking

The input is a singly linked list and a non-negative integer k.

Rotating the list to the right by k means taking the last k nodes, preserving their order, and moving them to the front.

For example, rotating 1 -> 2 -> 3 -> 4 -> 5 by 2 should produce 4 -> 5 -> 1 -> 2 -> 3.

The tricky part is that the list is singly linked. There is no direct pointer to the previous node, so any solution that repeatedly grabs the last node and moves it to the front ends up rescanning the list again and again.

The first idea most people try

The most obvious approach is to perform one rotation at a time:

1. walk to the end of the list
2. detach the last node
3. place it in front
4. repeat k times

That works, but it is inefficient. Each single rotation costs O(n) because the algorithm must find the node just before the tail. Repeating that k times leads to O(n * k) time, which is far too expensive when k is large.

That inefficiency points to the real insight: the answer does not depend on every individual rotation. It depends only on where the new break point ends up.

The key insight: rotation only depends on k % n

If the list length is n, then rotating right by n leaves the list unchanged.

That means:

• rotate by n -> same list
• rotate by 2n -> same list
• rotate by k -> same as rotate by k % n

So the first step is to compute the list length and reduce k to its effective rotation count.

Once that is done, the problem becomes much simpler:

• if k % n == 0, return the original list
• otherwise, find the new tail
• the node after the new tail becomes the new head

The only remaining question is how to reposition the pointers cleanly in one pass.

The optimal way to think about it

The cleanest derivation is to temporarily turn the list into a circle.

Suppose the list is:

1 -> 2 -> 3 -> 4 -> 5

If the tail points back to the head, it becomes:

1 -> 2 -> 3 -> 4 -> 5 -> 1 -> ...

Now a “rotation” is no longer a complicated operation. It is just choosing where to cut the circle.

If the effective right rotation is r, then:

• the new head is n - r steps from the current head
• the new tail is one node before that

So the algorithm is:

1. compute the length and find the tail
2. reduce k to k % n
3. connect tail.next = head to form a cycle
4. walk n - k - 1 steps from the old head to land on the new tail
5. set new_head = new_tail.next
6. break the cycle by setting new_tail.next = None

That gives an O(n) time solution with O(1) extra space.

How to derive this in an interview

A strong interview explanation usually looks like this:

1. Reject repeated single-step rotations because they rescan the list too many times.
2. Observe that full-list rotations change nothing, so only k % n matters.
3. Realize the final order is already present in the original list; only the split point changes.
4. Use the tail to connect the list into a temporary cycle.
5. Cut the cycle at exactly the node that should become the new tail.

This derivation is valuable because it turns what feels like pointer trickery into a simple structural idea: compute the effective shift, make the list circular, then cut once.

Python solution

The implementation below is self-contained and organized around small helper functions:

• compute_length_and_tail finds the two facts every solution needs
• find_new_tail walks to the node where the list should be cut
• rotate_right performs the actual rotation
• Solution.rotateRight matches LeetCode’s expected method name

from __future__ import annotations

from dataclasses import dataclass
from typing import Optional, Tuple


@dataclass
class ListNode:
    val: int = 0
    next: Optional["ListNode"] = None


def compute_length_and_tail(head: ListNode) -> Tuple[int, ListNode]:
    """Return the length of the list and its last node."""
    length = 1
    tail = head

    while tail.next is not None:
        tail = tail.next
        length += 1

    return length, tail


def find_new_tail(head: ListNode, steps_from_head: int) -> ListNode:
    """Walk a fixed number of steps from head and return that node."""
    current = head

    for _ in range(steps_from_head):
        assert current.next is not None
        current = current.next

    return current


def rotate_right(head: Optional[ListNode], rotation_count: int) -> Optional[ListNode]:
    """
    Rotate a singly linked list to the right.

    The algorithm computes the effective rotation, forms a temporary cycle,
    then breaks the cycle at the new tail.
    """
    if head is None or head.next is None or rotation_count == 0:
        return head

    length, tail = compute_length_and_tail(head)
    effective_rotation = rotation_count % length

    if effective_rotation == 0:
        return head

    # Form a circle so the rotated list becomes a single cut operation.
    tail.next = head

    steps_to_new_tail = length - effective_rotation - 1
    new_tail = find_new_tail(head, steps_to_new_tail)
    new_head = new_tail.next

    # Break the circle and return the new front of the list.
    new_tail.next = None
    return new_head


class Solution:
    def rotateRight(
        self, head: Optional[ListNode], k: int
    ) -> Optional[ListNode]:
        return rotate_right(head, k)

Why this works

After the list is connected into a cycle, every node still appears exactly once in the same relative order. The only thing that changes is where the cycle is cut.

If the effective rotation is r, then the last r nodes of the original list must move to the front. That means the new head must be the node at position n - r, and the node just before it must become the new tail.

Walking n - r - 1 steps from the original head lands exactly on that new tail. The next node is therefore the correct new head. Breaking the cycle there restores a standard singly linked list with the desired rotated order.

Nothing is lost, nothing is duplicated, and the relative order inside both segments is preserved, which is exactly what the problem requires.

Interview follow-ups

What if k is much larger than the list length?

The expected answer is that large k values should be reduced immediately with k % n, where n is the list length. A rotation by the full length returns the list to its original state, so any extra full cycles are irrelevant. This is the key optimization that turns a potentially huge number of conceptual rotations into one structural change. The time complexity remains O(n) because the algorithm still only needs one pass to compute the length and one partial pass to find the cut point.

Can this be solved without explicitly making the list circular?

Yes. An interviewer may ask for a two-pointer version. After computing the length and reducing k, one pointer can be advanced k steps ahead of another. Then both pointers move together until the front pointer reaches the tail. At that moment, the back pointer is on the new tail. The algorithm then rewires front.next to the original head, sets new_head = back.next, and cuts back.next = None. This has the same O(n) time and O(1) extra space complexity. The tradeoff is mostly stylistic: the circular-list solution is often easier to explain, while the gap-based two-pointer version may feel more natural to people who think in pointer offsets.

What if the list must be treated as immutable?

If the nodes cannot be rewired, then the in-place O(1) space solution is no longer allowed. The correct approach becomes building a new list in rotated order. A practical implementation would still compute n and k % n, determine the split point, and then copy nodes into a new list starting from the rotated head position. That preserves the same high-level reasoning but changes the space complexity to O(n) because the result must allocate new nodes. This is a good follow-up because it tests whether the candidate understands which part of the original solution depends on mutability.

What if the interviewer asks for left rotation instead of right rotation?

The same idea still works. A left rotation by k is equivalent to a right rotation by n - (k % n) when k % n != 0. After converting the request, the exact same circular-list algorithm can be reused. Another equally valid view is to say that for left rotation the new head is simply k % n steps from the original head, so the cut point moves accordingly. The complexity stays O(n) time and O(1) extra space because only the interpretation of the shift changes.

Practical takeaway

This is a good linked-list problem to remember because the final solution is simpler than it first appears.

The reusable pattern is:

• compute the list length
• reduce the problem with modulo arithmetic
• turn pointer rearrangement into a single cut point

Once that structure is clear, the implementation becomes short, deterministic, and easy to justify in an interview.