# LeetCode 206: Reverse Linked List

## Problem Restatement

We are given the head of a singly linked list.

We need to reverse the list and return the new head.

Example:

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

becomes:

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

The official statement says: given the `head` of a singly linked list, reverse the list, and return the reversed list.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Head of a singly linked list |
| Output | Head of the reversed linked list |
| Operation | Reverse every pointer direction |
| Important detail | The original head becomes the new tail |

Typical node definition:

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

Example function shape:

```python
def reverseList(head: ListNode) -> ListNode:
    ...
```

## Examples

Example 1:

```text
head = [1,2,3,4,5]
```

Result:

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

Example 2:

```text
head = [1,2]
```

Result:

```text
[2,1]
```

Example 3:

```text
head = []
```

Result:

```text
[]
```

## Understanding Pointer Reversal

Suppose we have:

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

Each node points forward.

To reverse the list, we want:

```text
1 <- 2 <- 3
```

The key operation is changing:

```text
current.next
```

Instead of pointing forward, it should point backward.

## The Main Difficulty

When we reverse a pointer, we risk losing the rest of the list.

Example:

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

If we immediately do:

```python
2.next = 1
```

without saving `3`, we lose access to the remaining nodes.

So before changing pointers, we must save the next node.

## Key Insight

At every step we need three pointers:

| Pointer | Meaning |
|---|---|
| `prev` | Previous node |
| `current` | Current node being processed |
| `next_node` | Saved next node |

Process:

```text
prev <- current -> next_node
```

We reverse:

```text
current.next = prev
```

Then move everything one step forward.

## Algorithm

1. Initialize:
   - `prev = None`
   - `current = head`
2. While `current` exists:
   1. Save the next node.
   2. Reverse the pointer.
   3. Move `prev` forward.
   4. Move `current` forward.
3. Return `prev`.

At the end, `prev` becomes the new head.

## Walkthrough

Initial list:

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

Start:

```python
prev = None
current = 1
```

### First iteration

Save next node:

```python
next_node = 2
```

Reverse pointer:

```text
1 -> None
```

Move pointers:

```python
prev = 1
current = 2
```

### Second iteration

Current structure:

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

Save:

```python
next_node = 3
```

Reverse:

```text
1 <- 2
```

Move forward:

```python
prev = 2
current = 3
```

### Final iteration

Reverse:

```text
1 <- 2 <- 3
```

Now:

```python
current = None
```

Loop ends.

Return:

```python
prev
```

which points to node `3`.

## Correctness

The algorithm maintains the invariant that:

- `prev` points to the already reversed portion of the list.
- `current` points to the remaining unreversed portion.

Initially:

```text
prev = None
current = head
```

So the reversed portion is empty.

At each iteration:

1. The algorithm saves the next node before modifying pointers.
2. It reverses the direction of `current.next`.
3. It extends the reversed portion by one node.
4. It advances to the next unreversed node.

No nodes are lost because the original next node is stored in `next_node`.

When the loop finishes, every pointer has been reversed, and `prev` points to the new head of the fully reversed list.

Therefore the algorithm correctly reverses the linked list.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | Each node is visited once |
| Space | `O(1)` | Only a few pointers are used |

## Iterative Implementation

```python
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        prev = None
        current = head

        while current:
            next_node = current.next

            current.next = prev

            prev = current
            current = next_node

        return prev
```

## Code Explanation

Start with:

```python
prev = None
current = head
```

`prev` represents the reversed part.

`current` represents the node being processed.

Save the next node before changing pointers:

```python
next_node = current.next
```

Reverse the pointer:

```python
current.next = prev
```

Move the pointers forward:

```python
prev = current
current = next_node
```

At the end:

```python
return prev
```

because `prev` points to the new head.

## Recursive Solution

We can also reverse the list recursively.

Idea:

1. Reverse the rest of the list.
2. Attach the current node at the end.

Example:

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

Recursive calls reverse:

```text
2 -> 3
```

into:

```text
3 -> 2
```

Then connect:

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

Implementation:

```python
class Solution:
    def reverseList(self, head: ListNode) -> ListNode:
        if not head or not head.next:
            return head

        new_head = self.reverseList(head.next)

        head.next.next = head
        head.next = None

        return new_head
```

## Recursive Code Explanation

Base case:

```python
if not head or not head.next:
    return head
```

A list with zero or one node is already reversed.

Reverse the remaining list:

```python
new_head = self.reverseList(head.next)
```

Suppose:

```text
head = 1
head.next = 2
```

After recursion:

```text
2 -> 1?
```

Now reverse the connection:

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

Break the old forward link:

```python
head.next = None
```

Return the final head:

```python
return new_head
```

## Testing

```python
def build_list(values):
    dummy = ListNode(0)
    current = dummy

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

    return dummy.next

def to_list(head):
    result = []

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

    return result

def run_tests():
    s = Solution()

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

    head = build_list([1,2])
    assert to_list(s.reverseList(head)) == [2,1]

    head = build_list([1])
    assert to_list(s.reverseList(head)) == [1]

    head = build_list([])
    assert to_list(s.reverseList(head)) == []

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| `[1,2,3,4,5]` | Standard reversal |
| `[1,2]` | Small list |
| `[1]` | Single node |
| `[]` | Empty list |