# LeetCode 92: Reverse Linked List II

## Problem Restatement

We are given the head of a singly linked list and two integers:

```python
left
right
```

The positions are 1-indexed.

We need to reverse the nodes from position `left` to position `right`, inclusive, and return the modified list.

Only that middle section should be reversed. The nodes before `left` and after `right` must stay in their original order.

The official statement asks us to reverse the nodes from position `left` to position `right` and return the reversed list. Example: `[1,2,3,4,5]`, `left = 2`, `right = 4` becomes `[1,4,3,2,5]`.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Head of a singly linked list, integer `left`, integer `right` |
| Output | Head of the modified linked list |
| Position rule | Positions are 1-indexed |
| Reversal range | Reverse nodes from `left` through `right` |
| Outside range | Keep all other nodes in the same order |

Function shape:

```python
class Solution:
    def reverseBetween(
        self,
        head: Optional[ListNode],
        left: int,
        right: int,
    ) -> Optional[ListNode]:
        ...
```

## Examples

Example 1:

```python
head = [1, 2, 3, 4, 5]
left = 2
right = 4
```

The section to reverse is:

```python
2 -> 3 -> 4
```

After reversal:

```python
4 -> 3 -> 2
```

The final list is:

```python
[1, 4, 3, 2, 5]
```

Example 2:

```python
head = [5]
left = 1
right = 1
```

There is only one node, so reversing the range changes nothing.

Answer:

```python
[5]
```

## First Thought: Copy Values Into an Array

A simple method is to copy all node values into an array.

Then reverse the slice:

```python
values[left - 1:right]
```

Then write the values back into the linked list.

This works, but it does not reverse the linked list nodes directly. It also uses extra memory.

We can solve it in-place by rewiring `next` pointers.

## Key Insight

The list has three parts:

```python
before left
left ... right
after right
```

Only the middle part changes direction.

A dummy node helps handle the case where `left = 1`.

```python
dummy -> head
```

We first move a pointer `prev` to the node just before position `left`.

Then we reverse the next `right - left + 1` nodes.

Finally, we reconnect the reversed section to the rest of the list.

## Algorithm

Create:

```python
dummy = ListNode(0, head)
```

Move `prev` to the node before the reversed section:

```python
prev = dummy
for _ in range(left - 1):
    prev = prev.next
```

Now:

| Pointer | Meaning |
|---|---|
| `prev` | Node before the reversed section |
| `cur` | First node inside the section |
| `tail` | The first node inside the section, which becomes the tail after reversal |

Reverse exactly `right - left + 1` nodes.

After reversal:

1. `prev.next` should point to the new head of the reversed section.
2. `tail.next` should point to the node after the reversed section.
3. Return `dummy.next`.

## Walkthrough

Use:

```python
head = [1, 2, 3, 4, 5]
left = 2
right = 4
```

Add dummy:

```python
dummy -> 1 -> 2 -> 3 -> 4 -> 5
```

Move `prev` to the node before position `2`:

```python
prev = node 1
```

The section starts at node `2`.

```python
prev -> 2 -> 3 -> 4 -> 5
```

Now reverse three nodes:

```python
2 -> 3 -> 4
```

During reversal, the links become:

```python
4 -> 3 -> 2
```

The node `2` becomes the tail of the reversed section.

Reconnect:

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

Return:

```python
[1, 4, 3, 2, 5]
```

## Correctness

The algorithm first places `prev` immediately before position `left`. Therefore, `prev.next` is the first node that must be reversed.

The reversal loop runs exactly `right - left + 1` times, so it reverses exactly the nodes in the target range and no others.

During the reversal, `cur` moves through the target section, and `new_head` becomes the head of the reversed section. The original first node of the section is saved as `tail`; after reversal, that node becomes the last node of the reversed section.

The node after the reversed range is saved as `cur` when the reversal loop finishes. Setting:

```python
tail.next = cur
```

connects the reversed section to the suffix of the original list.

Setting:

```python
prev.next = new_head
```

connects the prefix of the original list to the reversed section.

All nodes before `left` are untouched. All nodes after `right` are untouched. The middle section is reversed. Therefore, the returned list is correct.

## Complexity

Let:

```python
n = number of nodes
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We move through the list at most once |
| Space | `O(1)` | Only pointers are used |

## Implementation

```python
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def reverseBetween(
        self,
        head: Optional[ListNode],
        left: int,
        right: int,
    ) -> Optional[ListNode]:
        dummy = ListNode(0, head)

        prev = dummy
        for _ in range(left - 1):
            prev = prev.next

        tail = prev.next
        cur = prev.next
        new_head = None

        for _ in range(right - left + 1):
            nxt = cur.next
            cur.next = new_head
            new_head = cur
            cur = nxt

        prev.next = new_head
        tail.next = cur

        return dummy.next
```

## Code Explanation

The dummy node handles reversal starting at the head:

```python
dummy = ListNode(0, head)
```

Move `prev` to the node before `left`:

```python
prev = dummy
for _ in range(left - 1):
    prev = prev.next
```

Save the first node of the section:

```python
tail = prev.next
```

This node becomes the tail after reversal.

Start reversing from the same node:

```python
cur = prev.next
new_head = None
```

Reverse exactly the target section:

```python
for _ in range(right - left + 1):
    nxt = cur.next
    cur.next = new_head
    new_head = cur
    cur = nxt
```

After the loop:

| Pointer | Meaning |
|---|---|
| `new_head` | Head of the reversed section |
| `tail` | Tail of the reversed section |
| `cur` | First node after the reversed section |

Reconnect the prefix:

```python
prev.next = new_head
```

Reconnect the suffix:

```python
tail.next = cur
```

Return the real head:

```python
return dummy.next
```

## Testing

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

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

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

    return dummy.next

def to_list(head):
    values = []

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

    return values

def check(values, left, right, expected):
    s = Solution()
    head = build_list(values)
    result = s.reverseBetween(head, left, right)
    assert to_list(result) == expected

def run_tests():
    check([1, 2, 3, 4, 5], 2, 4, [1, 4, 3, 2, 5])
    check([5], 1, 1, [5])
    check([1, 2, 3], 1, 2, [2, 1, 3])
    check([1, 2, 3], 2, 3, [1, 3, 2])
    check([1, 2, 3], 1, 3, [3, 2, 1])
    check([1, 2], 1, 1, [1, 2])

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1, 2, 3, 4, 5]`, `2..4` | Main example |
| `[5]`, `1..1` | Single node |
| Reverse from head | Checks dummy node logic |
| Reverse to tail | Checks suffix reconnect |
| Reverse whole list | Checks both head and tail changes |
| `left == right` | No effective change |