p06 — Reverse Linked List

Source: LeetCode 206 · Easy · Topics: Linked List, Recursion Companies (2024–2025 frequency): Microsoft (very high), Amazon (very high), Meta (high), Apple (high), Google (medium), Bloomberg (high) Loop position: phone screen warmup; also the “first 5 min” of harder list problems (LC 25, LC 92, LC 234)

1. Quick Context

The linked-list version of FizzBuzz. The interviewer is not testing whether you can do it — they are testing whether you can do it without losing a node. The signature failure mode is curr = curr.next AFTER you’ve already overwritten curr.next to point backward — now you have no way to advance. Every “reverse in place” problem in interview lore (groups of K, reverse-between-indices, palindrome-check-by-reversing-half) reuses this kernel.

What it looks like it tests: linked list manipulation. What it actually tests: can you hold three references in your head at once and execute the swap in the right order under pressure? Many candidates know “use prev / curr / next” but write the four lines in the wrong order and silently produce a list of length 1.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/reverse-linked-list/

STOP. Set a 12-minute timer. Code BOTH the iterative and recursive versions in a scratch file. Do not read past this section until either is solved or the timer expired.

If you’ve done this before: do it again, and time only the iterative version. Target: 4 min, zero scratch paper, written correctly first try. The recursive version should follow in another 4 min. If iterative takes >6 min, you don’t have the three-pointer dance memorized — fix that before moving on.

3. Prerequisite Concepts

• Singly linked list node model: next pointer, sentinel None (phase-01 §4 Linked List Pointers)
• In-place mutation vs. allocation tradeoff: this problem can be solved by building a new list (O(N) extra space) OR by pointer rewiring (O(1) extra). Interviewers expect O(1).
• Recursion stack frame cost: the recursive version uses O(N) stack space; on real production systems this stack-overflows around N=10^4 in CPython without sys.setrecursionlimit bump.

4. How to Approach (FRAMEWORK Steps 1–9 applied)

Step 1 — Restate: “Given the head of a singly linked list, return the head of the same list with all next pointers reversed.”

Step 2 — Clarify:

• “Is the list empty? Single node?” (Both possible; handle separately.)
• “Should I mutate the input or return a new list?” (Mutate in-place is the expected answer; ask anyway.)
• “Doubly linked or singly?” (Singly per LC; doubly is a trivially different rewrite.)
• “Is there a risk of cycles in the input?” (No per LC, but in real production code this is a question worth asking.)

Step 3 — Constraints: N up to 5000 per LC. Both O(N) iterative and O(N) recursive fit. Iterative is preferred for space.

Step 4 — Examples:

• 1 → 2 → 3 → 4 → 5 → 5 → 4 → 3 → 2 → 1
• 1 → 2 → 2 → 1 (the smallest non-trivial case)
• 1 → 1 (single node — does your code crash on this?)
• None → None (empty list — does your code crash on this?)

Step 5 — Brute Force: Build a Python list of all values, walk it in reverse, build a new linked list. O(N) time, O(N) space. State this aloud, then propose the in-place version.

Step 6 — Brute Force Complexity: Time O(N), space O(N). Correct but rejects the “in-place” implicit requirement.

Step 7 — Pattern Recognition: “Mutate linked list pointers without losing nodes” → three-pointer dance (prev, curr, next_node). This is the kernel pattern; every harder linked-list problem reuses it.

Step 8 — Optimize: Three pointers. Initialize prev = None, curr = head. Loop: save next_node = curr.next BEFORE overwriting; rewrite curr.next = prev; advance prev = curr and curr = next_node. Stop when curr is None. Return prev.

Step 9 — Prove correctness: Loop invariant: after iteration k, the first k nodes of the original list have been reversed and form a sublist rooted at prev. The remaining N − k nodes form the original tail rooted at curr. When curr becomes None, all N nodes have been processed and prev is the new head.

5. Progressive Hints

If stuck for 5 minutes, open hints.md. One hint, 5-min timer, retry.

6. Deeper Insight — Why It Works

The fundamental constraint: a singly linked list only lets you traverse forward. To reverse, you need to remember the forward direction before destroying it. The next_node = curr.next save is not optional — it’s the entire trick. Without it, you overwrite curr.next to point backward, and then curr = curr.next walks you backward instead of forward, into infinite loop or off the tail.

Why exactly three pointers: you need prev (where to point backward to), curr (which node am I rewriting), and next_node (where to go after rewriting). Two pointers leaves you with the “lost the rest of the list” bug. Four pointers is overengineering.

Recursion’s elegance vs. cost: the recursive version is a one-liner expression: “reverse the rest, then make my old next point to me, then set my next to None.” It’s a clean expression of the invariant: reverse(head) returns the new head of the reversed sublist starting at head. The cost is O(N) stack frames — and the system stack is not a debugger-friendly place to be at N=10^5.

Why O(1) space matters in interviews: the iterative version proves you understand that linked lists are already using O(N) memory; allocating O(N) more is a doubling. The interviewer’s brain registers this as “this person thinks about memory.”

7. Anti-Pattern Analysis

Wrong-but-tempting #1 — Forget to save next_node first:

prev, curr = None, head
while curr:
    curr.next = prev      # we just lost access to the rest of the list
    prev = curr
    curr = curr.next      # this is now prev, infinite loop or crash

The single most common bug. Write the lines in the order: SAVE → REWIRE → ADVANCE-PREV → ADVANCE-CURR. Memorize this sequence.

Wrong-but-tempting #2 — Build a stack of values, then rebuild the list:

vals = []
while head:
    vals.append(head.val)
    head = head.next
# rebuild
dummy = ListNode()
curr = dummy
for v in reversed(vals):
    curr.next = ListNode(v)
    curr = curr.next
return dummy.next

Works, but: (a) O(N) extra space, (b) allocates N new nodes, doubling memory traffic, (c) telegraphs to the interviewer “I don’t know how to mutate pointers.” For a phone screen, you fail the “demonstrate pointer competence” signal.

Wrong-but-tempting #3 — Recursive without base case for empty:

def reverse(head):
    if head.next is None:    # crashes on head = None
        return head
    new_head = reverse(head.next)
    head.next.next = head
    head.next = None
    return new_head

Must guard if head is None or head.next is None. Many candidates write only the latter and crash on empty input.

Wrong-but-tempting #4 — Recursive but forget head.next = None: After head.next.next = head, the old tail still has head.next pointing forward, creating a cycle of length 2 at the tail. The result list has a cycle and every subsequent operation (length, traversal) hangs. This is a classic silent bug — the function returns, but the structure is corrupt.

8. Skills & Takeaways

Generalizable pattern: “Three-pointer in-place pointer rewrite.” Whenever you mutate a pointer that you also need to follow, save the destination FIRST. This pattern reappears in:

• LC 92 — Reverse Linked List II (reverse between indices)
• LC 25 — Reverse Nodes in k-Group (Hard; reuse this kernel inside a loop)
• LC 234 — Palindrome Linked List (reverse second half, compare)
• LC 143 — Reorder List (split, reverse second half, weave)
• LC 24 — Swap Nodes in Pairs (degenerate k=2 case)
• LC 86 — Partition List (rewires by partition; same caution about lost references)

When NOT to use this: Doubly linked list (you have prev pointers already, swap them in one step). Immutable / persistent list (build new structure; O(N) space is required).

9. When to Move On (binary; must all be YES)

• I wrote the iterative version in <5 min with zero pointer-loss bugs on the second attempt
• I wrote the recursive version and handled both empty and single-node bases
• I can recite the line order (SAVE → REWIRE → ADVANCE-PREV → ADVANCE-CURR) without looking
• I can explain why the recursive version sets head.next = None at the end (cycle prevention)
• My stress_test() in solution.py passes 1000 iterations on both versions
• I solved LC 92 (Reverse Linked List II) and recognized this kernel inside it
• I solved LC 234 (Palindrome Linked List) and saw why “reverse the second half” is the right move

If any unchecked: redo before moving to p07.

10. Company Context

Microsoft (loves this problem — phone-screen mainstay)

• The framing: “Reverse a singly linked list. Both iterative and recursive, please.”
• Misleading example: They show you 1 → 2 → 3 and you smash out the iterative version in 90 seconds. They then say: “Now do it recursively.” If you can’t, you lose senior signal.
• Adversarial extension: “Now reverse only the first K nodes” (LC 25 lead-in). Then “now in groups of K with the remainder left in original order.”
• What they want to hear: Verbal walkthrough of the three pointers BEFORE coding. Microsoft phone screens use this as a calibration tool — if you can’t articulate the dance, the loop position never opens.

Amazon (Leadership Principles + correctness)

• The framing: Often inside a story problem: “Given a list of order processing steps in reverse, return them in forward order.”
• Misleading example: [A, B, C] where you might be tempted to use a Python reversed() builtin. Amazon expects you to demonstrate the algorithm, not a one-liner.
• Adversarial extension: “What if the list is too large to fit in memory and we’re streaming it from disk?” → split into chunks, reverse each, then reverse the chunk order (external-sort-style thinking).
• What they want to hear: “Let me handle empty input first.” Amazon weights Customer Obsession heavily — and customers send empty inputs.

Meta (rapid-fire follow-ups)

• The framing: Reverse → palindrome check → reorder → reverse-in-K-groups, all in 25 minutes.
• Misleading example: Often starts with “given the head of a list, return it in reverse order” — ambiguous between “return values reversed” (O(N) space, trivial) and “reverse the structure in place.” Ask.
• Adversarial extension: “Reverse just the alternating nodes.” Now you maintain two interleaved sublists.
• What they want to hear: “Let me trace through a length-2 example to verify my pointer updates” — explicit dry-run before submission. Meta interviewers love the dry-run signal.

Google (recursive elegance matters here)

• The framing: Iterative is acceptable, but the follow-up is always “now do it recursively, and explain the stack-depth tradeoff.”
• Misleading example: They might give you a generic Node type with children: List[Node] (LC 116, 117 territory) — listen carefully whether it’s singly linked or n-ary.
• What they want to hear: Big-O analysis of stack depth. Phrase: “Recursive uses O(N) stack space; for N > 10^4 in production we’d switch to iterative or trampoline.”

Apple / Bloomberg (clarity above all)

• The framing: Often combined with “now print the list reversed without modifying it” — to test whether you can use a stack, OR walk and recurse, vs. mutate.
• What they want to hear: Clear distinction between “reverse the structure” and “iterate in reverse order.” Many candidates conflate these.

11. Interviewer’s Lens

The scorecard line that gets you the offer: “Demonstrated mastery of the three-pointer rewrite kernel; would pass it down to junior engineers.”

The scorecard line that loses you: “Lost a pointer mid-loop; required interviewer to debug; suggests inattention to detail.”

12. Level Delta

Honest self-assessment: Did you lose a pointer? If yes, you’re Mid. Did you handle empty without prompting? If yes, Senior floor. Did you mention the recursive cycle bug unprompted? Staff signal.

13. Follow-up Questions & Full Answers

Follow-up 1: “Now reverse the list recursively. What’s the space cost?”

Signal sought: Comfort with recursion + complexity literacy.

Full answer: “Base case: if head is None or head.next is None, return head. Recursive: new_head = reverse(head.next); this returns the new head of the reversed sublist starting from the second node. Then head.next.next = head makes the old second node point back to head, and head.next = None cuts the forward link to prevent a 2-cycle at the tail. Return new_head. Time O(N), space O(N) for the call stack. In CPython that stack-overflows around N=1000 by default; we’d raise sys.setrecursionlimit(10_000) or rewrite iteratively in production.”

Follow-up 2: “What if it’s a doubly linked list?”

Signal sought: Adaptation, not just memorization.

Full answer: “For each node, swap its prev and next pointers. After processing all nodes, the original tail is the new head — return it. Single pass, O(1) extra space, no save-then-rewire needed because we have prev access already. The code is dramatically simpler — which is the point: data structure shape determines algorithm shape.”

Follow-up 3: “What if I want to reverse only the middle K elements?” (LC 92)

Signal sought: Can you reuse the kernel inside a more complex algorithm?

Full answer: “Two phases. (1) Walk to the (left-1)th node, save it as before. (2) From the leftth node, reverse exactly right - left + 1 nodes using the same three-pointer dance. (3) Stitch: before.next.next = curr (the first reversed node’s next now points to what’s after the reversed segment); before.next = prev (the new head of the reversed segment). Use a dummy node before head to handle left = 1 uniformly. O(N) time, O(1) space.”

Follow-up 4 (Hard): “Reverse the list in groups of K. If the last group has fewer than K nodes, leave it in original order.” (LC 25)

Signal sought: Composition of the kernel under bookkeeping pressure.

Full answer: “Outer loop: at each group start, walk K nodes ahead to check there are at least K; if not, break and leave the rest alone. Inner loop: reverse exactly K nodes using the kernel. Stitch each reversed group to the previous group’s tail using a group_prev pointer. The whole algorithm is O(N) — each node is touched at most twice (once for the K-check, once for reversal). Edge cases: K=1 (no-op), K=N (full reverse), N % K != 0 (last partial group untouched).”

Follow-up 5 (Senior signal): “How would you test this?”

Signal sought: Testing as engineering discipline.

Full answer: “Four layers. (1) Unit: empty, single, two-node, length-N (small and large). (2) Round-trip property: reverse twice equals identity — strongest invariant test for any reversal. (3) Cycle detection on output: walk the result with Floyd’s; should terminate at None. This catches the head.next = None bug in the recursive version. (4) Memory profile under large N: confirm no node allocation in the iterative version. My solution.py includes the round-trip property test.”

14. Full Solution Walkthrough

See solution.py.

The file has five sections:

1. ListNode — minimal node class with __repr__ for debugging.
2. reverse_iterative(head) — the three-pointer dance with INVARIANT comment. This is the production-grade answer.
3. reverse_recursive(head) — for didactic comparison; bumps sys.setrecursionlimit for stress test.
4. stress_test() — generates 1000 random lists, runs both implementations, asserts round-trip property (reverse(reverse(x)) == x) and that values match expected reversal.
5. edge_cases() — empty, single, two-node, all-same-value, large.

Decisions justified in the file:

• Why we return prev not curr: at loop exit, curr is None and prev is the last node visited, which is the new head.
• Why iterative is preferred: O(1) space, no stack-overflow risk.
• Why next_node is a local variable per iteration, not a class field: scope discipline; only the inner loop needs it.

15. Beyond the Problem — Production Reality

At scale:

• In a network stack (Linux sk_buff chains, packet queues), reversing a packet list is real — e.g., for retransmission ordering. The iterative kernel is exactly what’s used; the kernel doesn’t tolerate stack-blowing recursion.
• In garbage collectors using Cheney’s algorithm, you walk and rewire pointers in-place as you copy — same “save the destination before overwriting” discipline.

Real systems this is the kernel of:

• Undo stacks: many text editors store edits as a linked list; “redo all undones” reverses the list.
• Compiler IR transformations: SSA phi-node reordering rewires successor lists in-place.
• Database transaction logs: replay order sometimes requires walking the WAL in reverse; if it’s a forward-only list on disk, you read it all, reverse the records list, and replay.

Principal-engineer code review comment: “The recursive version is elegant but I’d reject it in our codebase. Our linked lists can hit 10^5 elements in production payloads — we’ve seen stack overflows in similar code. The iterative version is what ships. Also: please add a debug assertion that the returned list has the same length as the input — we had a production incident where a reversal silently dropped a node due to a refactor of the loop guard.”