# 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](https://leetcode.com/problems/rotate-list/?utm_source=chatgpt.com))

## Input and Output

| Item | Meaning |
|---|---|
| Input | Head of a singly linked list and integer `k` |
| Output | Head of the rotated linked list |
| Rotation | Move the last node to the front |
| Direction | Right rotation |

Linked list node definition:

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

Function shape:

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

## Examples

For:

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

After one rotation:

```text
5 -> 1 -> 2 -> 3 -> 4
```

After two rotations:

```text
4 -> 5 -> 1 -> 2 -> 3
```

So the answer is:

```text
4 -> 5 -> 1 -> 2 -> 3
```

For:

```text
0 -> 1 -> 2
k = 4
```

The list length is `3`.

Rotating by `4` is the same as rotating by:

```python
4 % 3 = 1
```

So the answer is:

```text
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:

```python
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:

```text
1 -> 2 -> 3 -> 4 -> 5
```

Rotating right by `2` means:

```text
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:

```text
1 -> 2 -> 3
```

Rotate by `3`:

```text
1 -> 2 -> 3
```

Rotate by `6`:

```text
1 -> 2 -> 3
```

So we only care about:

```python
k % length
```

## Algorithm

Handle empty lists first.

Then:

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

```python
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

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | The list is traversed a constant number of times |
| Space | `O(1)` | Only pointers and counters are used |

## Implementation

```python
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:

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

Then compute the length and find the tail:

```python
length = 1
tail = head

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

Reduce unnecessary rotations:

```python
k %= length
```

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

```python
if k == 0:
    return head
```

Now connect the tail back to the head:

```python
tail.next = head
```

The list is now circular.

We need the new tail.

It is located:

```python
length - k - 1
```

steps from the original head.

Move to that node:

```python
new_tail = head

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

The next node becomes the new head:

```python
new_head = new_tail.next
```

Break the cycle:

```python
new_tail.next = None
```

Finally:

```python
return new_head
```

## Testing

```python
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()
```

| Test | Why |
|---|---|
| `[1,2,3,4,5]`, `k = 2` | Standard example |
| `[0,1,2]`, `k = 4` | Rotation larger than list length |
| Single node | Rotation should not change the list |
| Empty list | Edge case |
| `k = 0` | No rotation |