LeetCode 61: Rotate List

Problem Restatement

We are given the head of a singly linked list and an integer k.

We need to rotate the list to the right by k places.

A right rotation means:

1. Remove the last node.
2. Move it to the front.

Repeat this process k times.

The official constraints are 0 <= number of nodes <= 500, -100 <= Node.val <= 100, and 0 <= k <= 2 * 10^9. (leetcode.com)

Input and Output

Linked list node definition:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Function shape:

def rotateRight(head: ListNode, k: int) -> ListNode:
    ...

Examples

For:

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

After one rotation:

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

After two rotations:

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

So the answer is:

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

For:

0 -> 1 -> 2
k = 4

The list length is 3.

Rotating by 4 is the same as rotating by:

4 % 3 = 1

So the answer is:

2 -> 0 -> 1

First Thought: Rotate One Step at a Time

One direct approach is:

1. Find the last node.
2. Remove it.
3. Move it to the front.
4. Repeat k times.

This works, but each rotation requires scanning the list to find the last node.

If the list has n nodes, each rotation costs O(n).

Doing that k times gives:

O(n * k)

That is too slow when k is large.

Key Insight

A linked list rotation is really a cut-and-reconnect operation.

Suppose:

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

Rotating right by 2 means:

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

The new head becomes the (n - k)th node from the front.

Instead of rotating repeatedly:

1. Compute the list length.
2. Connect the tail back to the head, forming a cycle.
3. Find the new tail.
4. Break the cycle.

This solves the problem in one traversal.

Reduce k

Rotating by the list length changes nothing.

For example:

1 -> 2 -> 3

Rotate by 3:

1 -> 2 -> 3

Rotate by 6:

1 -> 2 -> 3

So we only care about:

k % length

Algorithm

Handle empty lists first.

Then:

1. Traverse the list once to compute the length and find the tail.
2. Compute:

k %= length

3. If k == 0, return the original list.
4. Connect the tail to the head to form a cycle.
5. Move length - k - 1 steps from the head to find the new tail.
6. The node after the new tail becomes the new head.
7. Break the cycle.

Correctness

Let the list length be n.

Rotating right by k moves the last k nodes to the front while preserving their order. After reducing with k %= n, we only need to consider 0 <= k < n.

The new head must therefore be the node originally at position n - k. The node immediately before it becomes the new tail.

The algorithm first connects the original tail to the original head, forming a cycle. This preserves the relative order of all nodes while allowing the list to wrap around naturally.

Then the algorithm walks n - k - 1 steps from the original head. This reaches the node immediately before the desired new head, so this node is the correct new tail.

The node after the new tail is assigned as the new head. Breaking the cycle after the new tail restores a valid singly linked list with exactly the required rotation.

Therefore the algorithm returns the correctly rotated list.

Complexity

Implementation

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

        if not head or not head.next or k == 0:
            return head

        length = 1
        tail = head

        while tail.next:
            tail = tail.next
            length += 1

        k %= length

        if k == 0:
            return head

        tail.next = head

        steps = length - k - 1
        new_tail = head

        for _ in range(steps):
            new_tail = new_tail.next

        new_head = new_tail.next

        new_tail.next = None

        return new_head

Code Explanation

First, handle trivial cases:

if not head or not head.next or k == 0:
    return head

Then compute the length and find the tail:

length = 1
tail = head

while tail.next:
    tail = tail.next
    length += 1

Reduce unnecessary rotations:

k %= length

If the reduced rotation is zero, the list stays unchanged:

if k == 0:
    return head

Now connect the tail back to the head:

tail.next = head

The list is now circular.

We need the new tail.

It is located:

length - k - 1

steps from the original head.

Move to that node:

new_tail = head

for _ in range(steps):
    new_tail = new_tail.next

The next node becomes the new head:

new_head = new_tail.next

Break the cycle:

new_tail.next = None

Finally:

return new_head

Testing

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def build(values):
    dummy = ListNode()
    cur = dummy

    for v in values:
        cur.next = ListNode(v)
        cur = cur.next

    return dummy.next

def to_list(head):
    ans = []

    while head:
        ans.append(head.val)
        head = head.next

    return ans

def run_tests():
    s = Solution()

    head = build([1, 2, 3, 4, 5])
    assert to_list(s.rotateRight(head, 2)) == [4, 5, 1, 2, 3]

    head = build([0, 1, 2])
    assert to_list(s.rotateRight(head, 4)) == [2, 0, 1]

    head = build([1])
    assert to_list(s.rotateRight(head, 99)) == [1]

    head = build([])
    assert to_list(s.rotateRight(head, 3)) == []

    head = build([1, 2])
    assert to_list(s.rotateRight(head, 0)) == [1, 2]

    print("all tests passed")

run_tests()