3.4 Reversal

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

a -> b -> c -> d -> null

the result is

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.

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:

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

After first iteration:

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

After second iteration:

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

After final iteration:

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

The final result is prev.

Why Order Matters

The line

next = cur.next

must happen before

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.

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

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

head.next.next = head

flips the edge between head and head.next.

Complexity

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

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:

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.