Rotate List

A right rotation looks repetitive when described one node at a time. The useful implementation is one split, one reconnection, and one cut.

The Short Answer: Find the Split

A right rotation moves the final k nodes to the front while preserving the order inside both parts.

1 -> 2 -> 3 -> 4 -> 5,  k = 2
4 -> 5 -> 1 -> 2 -> 3

The direct Rotate List solution is:

1. Traverse the list to find its length and tail.
2. Reduce k with k % length.
3. If the effective rotation is zero, return the original head.
4. Connect the old tail to the old head, creating a temporary cycle.
5. Find the node that should become the new tail.
6. Save the node after it as the new head.
7. Cut the new tail's next pointer.
8. Return the new head.

The existing nodes are rewired in place. No array of values is needed, and the algorithm uses O(1) auxiliary space.

The central question is not “How do I move the last node k times?” It is:

Where should the final list be cut so the suffix becomes the new prefix?

Recognize Rotation as a Cycle Cut

A natural first attempt is to rotate right by one repeatedly:

• Find the last node.
• Detach it.
• Put it before the current head.
• Repeat k times.

That approach matches the definition, but it repeats the expensive part: finding the tail. If k is large, the list gets scanned again and again.

There is an immediate reduction:

[ k_{\text{effective}} = k \bmod n ]

where n is the number of nodes.

Why is this valid? A list of length n returns to its original order after exactly n right rotations. Rotating by n + 1 places is therefore the same as rotating by 1, and rotating by 2n places changes nothing.

After normalization, the result has two contiguous segments:

original:  [prefix of length n - k] [suffix of length k]
result:    [suffix of length k]      [prefix of length n - k]

For:

1 -> 2 -> 3 -> 4 -> 5
k = 2

the prefix is:

1 -> 2 -> 3

and the suffix is:

4 -> 5

The suffix moves to the front, but neither segment changes its internal order.

Using zero-based positions, the new tail is at:

[ n - k_{\text{effective}} - 1 ]

The node after that position is the new head.

This is a linked-list cycle cut, not primarily a Fast & Slow Pointers problem. Two pointers can solve many linked-list tasks, but the important signal here is different: rotation preserves two ordered segments, so temporarily join the end to the beginning and cut at the derived boundary.

Name the Pointer Obligations

Before changing any next pointer, assign each variable a job.

• tail identifies the final node in the original acyclic list.
• length counts the original nodes.
• effective_k removes complete rotations.
• new_tail identifies where the final list must end.
• new_head preserves the node that will begin the returned list.

Start by scanning the original list:

head -> ... -> tail -> None

This scan must happen before creating the cycle. Otherwise, a later traversal would never encounter None, and the length calculation could loop forever.

Handle an empty list before dereferencing head or calculating a modulo:

if head is None:
    return head

There is no valid length for an empty list, so k % length would also be invalid.

Once the length is known, normalize k:

effective_k = k % length

If effective_k == 0, the list already has the required order. Return immediately. This includes:

• k == 0
• k divisible by length
• every rotation of a singleton list

For a nonzero rotation, connect the original tail to the original head:

tail.next = head

The structure is now circular:

1 -> 2 -> 3 -> 4 -> 5
^                   |
|___________________|

No node has become unreachable. Every original successor relationship is still available, and the old tail now leads into the old head.

Next, locate the new tail. From the original head, advance length - effective_k - 1 times. That lands on the final node of the prefix. Its successor is the first node of the suffix, which becomes the new head.

The mutation order matters:

new_head = new_tail.next
new_tail.next = None

Save new_head first. If you cut the link before saving it, the suffix is no longer reachable from new_tail, and you may lose the only reference to the returned list.

Pointer rule: Before a destructive write, save every successor that the result still needs.

The final structure is:

new_head -> ... -> tail -> old_head -> ... -> new_tail -> None

The cycle is gone, and the list boundary has moved.

Prove the Rewiring

Let the original list be partitioned into:

• a prefix from head through new_tail
• a suffix from new_head through tail

Their lengths are:

prefix length = n - effective_k
suffix length = effective_k

The original list preserves the order within each segment:

prefix -> suffix

After setting:

tail.next = head

the cycle creates this traversal:

prefix -> suffix -> prefix -> suffix -> ...

The suffix still flows into the prefix because the old tail now points to the old head. Nothing inside either segment was reversed or rearranged.

The new tail is the node immediately before the desired new head. When we set:

new_tail.next = None

we turn the cycle into a linear list:

suffix -> prefix

That is exactly a right rotation by effective_k.

The boundary-search invariant is simple:

As new_tail advances from the original head, it remains at the node that precedes the eventual new head after the required number of steps.

For a list of length n, the new tail is at index n - effective_k - 1. The node after it is therefore at index n - effective_k, which is the first node of the final suffix.

The postcondition is stronger than “the values look correct”:

1. Every original node is reachable from the returned head.
2. Every original node is reachable exactly once.
3. The final node points to None.
4. The relative order inside the moved suffix is preserved.
5. The relative order inside the remaining prefix is preserved.

That last check matters. A malformed cycle can produce the expected first few values while still failing when the judge traverses the entire result.

Dry-Run the Boundary

Use:

1 -> 2 -> 3 -> 4 -> 5 -> None
k = 2

1. Count and normalize

The length is:

n = 5

The effective rotation is:

effective_k = 2 % 5 = 2

The new tail position is:

n - effective_k - 1
= 5 - 2 - 1
= 2

With zero-based indexing, position 2 is node 3.

So:

new_tail = 3
new_head = 4

2. Close the cycle

Connect the old tail to the old head:

1 -> 2 -> 3 -> 4 -> 5
^                   |
|___________________|

The edge 5 -> 1 lets the suffix flow into the prefix.

3. Save and cut

Save:

new_head = new_tail.next = 4

Then cut:

3.next = None

The remaining edges are:

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

The result is a right rotation by two places.

A common off-by-one mistake is to stop at node 4, the new head, instead of node 3, the new tail. The new tail owns the boundary: it is the node whose next pointer must become None.

Another mistake is mixing traversal conventions. If you start at head, advance n - k - 1 steps. If you start at the old tail after closing the cycle, you can use a different step count. Both approaches work, but switching formulas without switching the starting point produces a wrong split.

Modulo reduction also matters:

0 -> 1 -> 2,  k = 4

Here:

n = 3
effective_k = 4 % 3 = 1

The result is:

2 -> 0 -> 1

There is no reason to perform four physical rotations. The list only needs one structural shift.

Implement the Python Solution

The implementation below uses the same variable names as the derivation. That is deliberate: in an interview, readable state is more valuable than compressed cleverness.

class Solution:
    def rotateRight(self, head: "ListNode", k: int) -> "ListNode":
        # An empty list has no length and no tail to inspect.
        if head is None:
            return head

        # Find the original tail and count the nodes.
        tail = head
        length = 1

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

        # Full rotations cancel out.
        effective_k = k % length

        if effective_k == 0:
            return head

        # Temporarily make the list circular.
        tail.next = head

        # The node at this position becomes the new tail.
        new_tail = head
        for _ in range(length - effective_k - 1):
            new_tail = new_tail.next

        # Save the new head before cutting the cycle.
        new_head = new_tail.next
        new_tail.next = None

        return new_head

The scan starts with:

tail = head
length = 1

That counting convention treats the head as the first node. The loop advances only while tail.next exists, so when it stops, tail is the original final node.

The structural sequence is also intentional:

1. Find tail and length.
2. Normalize k.
3. Return for a zero rotation.
4. Close the cycle.
5. Find new_tail.
6. Save new_head.
7. Cut the cycle.
8. Return.

Do not move the modulo operation before the empty-list check. Do not cut before saving new_head. Do not create the cycle for a zero rotation; the early return avoids unnecessary mutation and reduces the number of states you must debug.

The judge is assumed to provide the usual ListNode definition. The algorithm changes node links, not node values, so it satisfies the in-place requirement.

Complexity and Edge-Case Audit

The first traversal finds both the length and the tail in O(n) time.

The boundary search advances at most n - 1 positions, which is another O(n) traversal in the worst case. The total time is therefore:

[ O(n) ]

The algorithm stores only a fixed number of pointers and integers:

[ O(1) ]

auxiliary space, excluding the existing linked-list nodes.

Use this audit before submitting:

Case	Expected behavior
Empty list	Return None without dereferencing head
Singleton list	Return the same node
k == 0	Return the original head
k % n == 0	Return the original head
k == 1	Move only the old tail to the front
k == n - 1	Move every node except the original head to the front
k > n	Reduce with modulo before locating the split

Test node identity as well as values. A solution can print the right sequence temporarily and still leave a cycle behind. The final traversal must terminate at None, and every original node must appear exactly once.

The most dangerous bugs are structural:

• forgetting to connect tail.next to head
• choosing the new head instead of the new tail as the cut point
• using an inconsistent off-by-one formula
• overwriting new_tail.next before saving it
• returning the old head after the rotation
• leaving new_tail.next connected and returning a cyclic list

The Transferable Pattern

When a linked-list operation moves a contiguous suffix or prefix while preserving the internal order of both parts, look for a split plus reconnection.

For this problem:

1. Count the nodes.
2. Reduce k modulo the length.
3. Identify the new tail position.
4. Temporarily close the list into a cycle.
5. Save the new head.
6. Cut the cycle.
7. Confirm every node is reachable exactly once.

That is the pattern worth carrying into the next interview. Repeated local movement may describe the operation, but one deliberate boundary change often implements it.