# 3.4 Reversal

Reversal transforms a linked list so that the direction of all edges is flipped. For a list

```text
a -> b -> c -> d -> null
```

the result is

```text
d -> c -> b -> a -> null
```

The operation is structural. No values change. Only the `next` pointers are reassigned.

## Problem

Given the head of a singly linked list, reverse the list in place and return the new head.

## Iterative Solution

The standard solution uses three pointers.

```text
prev = null
cur = head

while cur != null:
  next = cur.next
  cur.next = prev
  prev = cur
  cur = next

head = prev
```

## Invariant

At every step:

* `prev` points to a fully reversed prefix
* `cur` points to the remaining suffix
* no nodes are lost

This invariant ensures that after each iteration, the structure remains a valid list, split into two parts.

## Execution Trace

Initial state:

```text
prev = null
cur = a -> b -> c -> d
```

After first iteration:

```text
prev = a -> null
cur = b -> c -> d
```

After second iteration:

```text
prev = b -> a -> null
cur = c -> d
```

After final iteration:

```text
prev = d -> c -> b -> a -> null
cur = null
```

The final result is `prev`.

## Why Order Matters

The line

```text
next = cur.next
```

must happen before

```text
cur.next = prev
```

Otherwise the rest of the list becomes unreachable. This is the most common failure mode.

## Recursive Solution

Reversal can also be defined recursively.

```text
reverse(head):
  if head == null or head.next == null:
    return head

  new_head = reverse(head.next)

  head.next.next = head
  head.next = null

  return new_head
```

## Recursive Invariant

The recursive call

```text
reverse(head.next)
```

returns a fully reversed list of the suffix. The current node `head` must then be attached to the end of that reversed suffix.

The line

```text
head.next.next = head
```

flips the edge between `head` and `head.next`.

## Complexity

| Method    | Time |      Space |
| --------- | ---: | ---------: |
| Iterative | O(n) |       O(1) |
| Recursive | O(n) | O(n) stack |

The iterative method is preferred in most systems due to constant space.

## Reversal with Sentinel

A dummy node is not necessary for full reversal, but it can simplify partial operations. For example, reversing a prefix can be expressed by detaching the segment, reversing it, and reconnecting through a sentinel.

## Reverse First k Nodes

```text
prev = null
cur = head
count = 0

while cur != null and count < k:
  next = cur.next
  cur.next = prev
  prev = cur
  cur = next
  count += 1

head.next = cur
head = prev
```

Here:

* `prev` becomes the new head of the reversed segment
* the original head becomes the tail of the segment
* `cur` points to the remaining suffix

## Reverse Between Positions

Reversal of a sublist `[m, n]` follows a similar pattern but requires locating the node before position `m`.

A sentinel simplifies this setup:

```text
dummy.next = head
prev = dummy

for i in 1..m-1:
  prev = prev.next
```

Then reverse the segment starting at `prev.next`.

## Common Failure Modes

* Forgetting to store `next` before rewiring
* Losing access to the remaining list
* Not reconnecting the tail after partial reversal
* Returning the wrong head
* Mixing up `prev` and `cur` roles

## Key Insight

Reversal is a local operation repeated globally. Each step moves one node from the original direction into the reversed direction. The algorithm works because it maintains a strict separation between processed and unprocessed parts, and never breaks reachability.

This pattern appears in many variants: reversing in groups, reversing sublists, and restructuring linked data in place.