Lab 04 — Linked List Pointers: Reverse Linked List

Goal

Master pointer manipulation under aliasing, the classic three-pointer iterative reverse, the recursive variant with stack-frame analysis, and the dummy-node technique. The deliverable: reverse a singly linked list iteratively and recursively, articulating exactly which references move when, and identifying the recursion-depth risk on long lists.

Background Concepts

Pointers as references; aliasing; null sentinels; recursion stack frames; tail-call elimination (or absence thereof). Review the Linked Lists section of the Phase 1 README, plus runtime concepts 3 (value vs reference) and 10 (recursion depth).

Interview Context

Reverse Linked List is the warm-up question at every FAANG. The signal isn’t whether you can do it — most candidates can — it’s whether you can do it cleanly, in two ways, on the whiteboard, while talking through pointer movement. It’s also the “are you ready for harder linked-list problems” gate.

Problem Statement

Given the head of a singly linked list 1 → 2 → 3 → 4 → 5 → null, return the head of the reversed list 5 → 4 → 3 → 2 → 1 → null. The original list nodes are reused (no new node allocation).

Constraints

0 ≤ N ≤ 5000 (LeetCode classic) — but realistic interview lists may have N up to 10⁵; recursion depth matters.
-5000 ≤ node.val ≤ 5000 (irrelevant for traversal logic).

Clarifying Questions

Is the list singly or doubly linked? (Singly — affects whether we need to update prev pointers.)
Is head ever null? (Yes — return null. Top edge case.)
Single-node list? (Return the same node; its next is already null.)
Should the reversal be in place (reuse nodes) or allocate new nodes? (In place is the standard; allocating new nodes is a different problem.)
Should I also support reversing a segment [m, n]? (That’s a follow-up — see “Reverse Linked List II”.)

Examples

Input	Output
`1 → 2 → 3 → 4 → 5`	`5 → 4 → 3 → 2 → 1`
`1 → 2`	`2 → 1`
`1`	`1`
`null`	`null`

Initial Brute Force

Walk the list, push values onto a stack, walk again and reassign values from the stack.

def reverse_brute(head):
    vals = []
    cur = head
    while cur:
        vals.append(cur.val)
        cur = cur.next
    cur = head
    while cur:
        cur.val = vals.pop()
        cur = cur.next
    return head

Brute Force Complexity

Time: O(N). Space: O(N) auxiliary. Two passes. Doesn’t reverse pointers — only mutates values, which violates the spirit (and breaks if val is immutable, e.g., final field).

Optimization Path

We want O(1) extra space by manipulating pointers directly. Two canonical approaches:

Iterative three-pointer: prev, cur, next. Walk forward, flip cur.next to prev, advance.
Recursive: reverse the tail, then attach the head behind it. Beautiful but O(N) stack.

Iterative is preferred for production (no stack-overflow risk). Recursive is preferred for explaining the idea. Strong candidates write both.

Final Expected Approach

Iterative, three pointers.

def reverse_list(head):
    prev = None
    cur = head
    while cur:
        nxt = cur.next   # save the rest of the list
        cur.next = prev  # flip
        prev = cur       # advance prev
        cur = nxt        # advance cur
    return prev          # prev is the new head

Recursive form:

def reverse_list_rec(head):
    if head is None or head.next is None:
        return head
    new_head = reverse_list_rec(head.next)
    head.next.next = head
    head.next = None
    return new_head

Data Structures Used

The input list itself; three local pointers. No new allocation.

Correctness Argument

Iterative invariant: before each iteration, the sub-list ending at prev is fully reversed and cur points at the head of the not-yet-reversed remainder. The body of the loop preserves the invariant: we save cur.next, flip cur.next to point at the reversed prefix, then advance prev and cur by one. When cur is None, the entire input has been processed and prev is the head of the reversed list.

Recursive correctness: by induction on length. Base: list of length 0 or 1 is its own reverse. Inductive step: assume reverse_list(head.next) correctly returns the head of the reversed tail. The original head is now at the end of the reversed tail; head.next is the last node of the reversed-tail (the original second node). Set head.next.next = head to append head; set head.next = None to terminate.

Complexity

Iterative: O(N) time, O(1) space. Recursive: O(N) time, O(N) space due to the call stack.

Implementation Requirements

Three named pointers: prev, cur, nxt (or next — but watch out for shadowing built-ins in some languages).
Initialize prev = null. Top bug: forgetting this means the head’s next becomes self-referential or stale.
Save cur.next before overwriting it. Forgetting to save loses the rest of the list.
Return prev, not cur (which is null at termination).
For recursion: handle the base case at head is None first.

Tests

Smoke: 1 → 2 → 3 → 4 → 5.
Unit: length 1, length 2, length 3.
Edge: null head; list with all-equal values; list with cycle (should not be passed in — but if defensive, detect with Floyd’s).
Large: N = 10⁵; if recursive, expect StackOverflow in Java/Python without sys.setrecursionlimit.
Random: build random lists, reverse, reverse again, assert equality with the original.
Invalid: ensure the original head’s next is null after reversal (it’s now the tail).

Follow-up Questions

“Reverse a sublist [m, n].” → “Reverse Linked List II” — needs a dummy node and careful pointer wiring.
“Reverse in groups of K.” → “Reverse Nodes in K-Group” — apply the iterative reverse on each chunk.
“Reverse a doubly linked list.” → swap prev/next per node.
“Detect and handle a cycle before reversing.” → Floyd’s tortoise and hare.
“Iterative without saving next (write it as a swap).” → trickier; usually a teaching exercise.
“Why is iterative preferred in production?” → no stack-overflow risk on long lists.

Product Extension

A document undo/redo stack implemented as a linked list. To replay actions in reverse temporal order, you reverse the list. In-place reversal is preferred because the list nodes carry references to large objects (action payloads) and reallocation would be expensive. The null-handling and dummy-node patterns transfer directly to LRU-cache implementations and free-list management.

Language/Runtime Follow-ups

Python: no tail-call elimination; sys.setrecursionlimit(N+100) for deep lists. Default recursion limit is 1000.
Java: typical stack ~500K frames; expect StackOverflowError for recursive on N=10⁵+.
Go: stack starts small (8 KB) and grows automatically. Recursion is safe for moderate N. Pointers are explicit (*ListNode).
C++: stack usually 1–8 MB; recursive risk depends. Use -fsanitize=address to catch use-after-free if you mis-rewire.
JS/TS: V8 doesn’t reliably tail-call optimize. Iterative is the only safe choice for large N.
Pointer aliasing: mutating cur.next while another reference (e.g., head) still points to the same node is exactly the operation we want — but only because we intentionally preserve the old next in nxt first.

Common Bugs

Losing the rest of the list — overwriting cur.next before saving it. Symptoms: list has 2 elements after “reverse.” Fix: always save first.
Forgetting to set the original head’s next to null — in recursive form, omitting head.next = None makes the original head point at itself or its successor, creating a cycle.
Returning head instead of prev — returns the now-tail of the reversed list. Always return prev.
Initializing prev to head instead of null — first iteration creates a self-loop.
Using next as a variable name in Python — shadows the built-in iterator function. Harmless here but tags you as junior.

Debugging Strategy

Hand-trace on a 3-node list. Draw arrows. After each iteration, write down where prev, cur, nxt point.
After running, walk the result and assert it terminates at null within N steps (cycle check).
If output is shortened (only 1 element), you lost the rest — debug the save step.
If output reverses but the last element points back to the previous, you forgot the head.next = None (recursive only).

Mastery Criteria

Wrote the iterative version cleanly in under 90 seconds.
Wrote the recursive version on demand and explained the inductive correctness argument.
Identified the null head and length-1 edge cases without prompting.
Stated why iterative is safer for production.
Drew the three-pointer dance on a whiteboard (or in comments) for one full iteration.
Acknowledged that recursive depth = N and called out the stack risk.

LeetCode Interview — Extreme Coding