Reverse Linked List

Reverse a singly linked list.

Why this is worth learning

Reversal consumes the original forward chain while constructing a backward chain. Saving the next pointer is what prevents a destructive write from losing the unread suffix.

Before coding: one-minute experiment

Why must next be saved before assigning cur.Next=prev?

Function signature

func ReverseList(head *ListNode) *ListNode

Inputs / outputs

• head: head of the list.
• Return: new head of the reversed list.

Example

1 -> 2 -> 3 -> nil
Output: 3 -> 2 -> 1 -> nil

Constraints

• 0 <= number of nodes <= 100_000

Core idea (near-solution)

An array of original node pointers gives a straightforward solution: reconnect them in reverse index order. To remove that O(n) storage, ask what information the next pointer assignment destroys. Replacing cur.Next loses the route to the untouched suffix unless its original successor is saved first. Keep the completed reversed prefix in prev and the untouched suffix in cur; save the next node, move cur into the prefix, and advance through the saved pointer. Allocating reversed values would solve a different identity contract.

Invariant: prev is the reversed list so far; curr is the remaining list.

Algorithm (step-by-step)

1. Initialize prev = nil, curr = head.
2. While curr != nil:
   • Save next = curr.Next.
   • Point curr.Next to prev.
   • Move prev to curr, curr to next.
3. Return prev.

Correctness sketch

Before each iteration, prev heads the reversed processed prefix and cur heads the untouched original suffix; together they contain all original nodes exactly once. Save cur.Next before changing it. Redirecting cur.Next to prev moves exactly the first suffix node onto the reversed prefix. Advancing prev to cur and cur to the saved next restores the invariant with one fewer unread node. The new edge points only into the processed prefix, so it cannot create a cycle with the untouched suffix. When cur is nil, prev heads all nodes in reverse order and is the required new head.

Trace (hand walkthrough)

Example input:
1 -> 2 -> 3 -> nil
Output: 3 -> 2 -> 1 -> nil

Walk:
- prev=nil, curr=1 -> 1->nil
- curr=2 -> 2->1->nil
- curr=3 -> 3->2->1->nil

Pitfalls to avoid

• Losing the next pointer before rewiring.

Debugging lens

Assert exact pointer order, not just reversed values. Include equal-valued nodes so a value-swapping implementation cannot masquerade as node reversal.

Complexity

• Time: O(n)
• Extra space: O(1)

Implementation notes (Go)

• Store next := cur.Next before rewiring.
• Update cur.Next = prev, then advance prev, cur.

Reconstruction checkpoint

Two callers hold different heads that share a suffix of original node objects. A new requirement says reverse one caller’s list while the other caller must still see its original Next chain. Can ordinary in-place reversal satisfy both? Explain the contract choice.

Return to Linked List · Module quiz