What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 12 patterns and 180 archetypes is 100% free to access with no credit card required. Students receive 40 free compute coins upon registration, +20 daily login coins, and +25 referral coins. A 24-hour unlimited AI coaching pass costs only 5 coins. Alternatively, developers can use Bring-Your-Own-Key (BYOK) for completely free unlimited AI coaching with personal Gemini or OpenAI keys. There are no recurring subscription fees.

What is the refund and cancellation policy?

Hi👋SpeedAlgo has zero recurring subscriptions, zero automatic renewals, and zero hidden billing traps. Because the core platform and learning materials are free, students never face unwanted credit card charges or recurring payment obligations.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo enforces deliberate practice: proving invariants, articulating Big-O tradeoffs, managing edge cases, and defending algorithmic approaches to a Senior SWE AI Mock Coach in an integrated Monaco code editor.

31. Linked List Reversal: Reverse Linked List (LC 206) • Invariant Proof & Speed-Run

Theory Context•Two Pointers & Sliding Window

EasyLC 206

Reverse Linked List (LeetCode 206)

You will see how one forward walk with prev, curr and a saved nxt turns every link of a list around without copying a node.

Target Frequency:AmazonAppleGoogleMetaMicrosoft

You get head, the first node of a singly linked list. Each node holds a value val and a pointer next to the node after it; the last node's next is None, and an empty list has head = None.

Turn the list around: the node that was last must come first, and every node must point to the one that used to come before it. Return the first node of the reversed list (None for an empty list, written []).

Follow-up: once you have one version, write the other one too, a loop and a recursive function.

Worked Examples

Example 1

Input:head = [1,2,3,4,5]

Output:[5,4,3,2,1]

Explanation: Every link now points the other way, so `5`, the old last node, is the new head and `1` ends the list.

Example 2

Input:head = [1,2]

Output:[2,1]

Explanation: `2` now points to `1`, and `1` points to `None`.

Example 3

Input:head = []

Output:[]

Explanation: An empty list has nothing to turn around, so the answer is the empty list.

⚖️Formal Constraints & Bounds

The number of nodes in the list is in the range [0, 5000].
-5000 <= Node.val <= 5000

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Only the direction of each next pointer changes, so one forward walk that saves the next node, flips the current link and steps on reverses the whole list in place, without creating or copying a single node.

Real-World Scenario & Production Applications

Many systems keep history as a chain where each entry points to the one before it: an undo log, a version chain, a free list inside a memory allocator. To replay such a chain oldest-first you need the links pointing the other way. When the next pointer lives inside the object itself (an intrusive list, common in operating-system kernels), flipping the links in place does this without allocating a second list.

Step-by-Step Execution Trace Table

Input head = [1,2,3,4,5] (LeetCode Example 1). Before each step, prev heads the reversed part and curr heads the untouched part:

Step	`curr`	`nxt = curr.next`	`curr.next = prev`	Reversed part (from `prev`) after the step	Untouched part (from `curr`) after the step
1	`1`	`2`	`1 -> None`	`1 -> None`	`2 -> 3 -> 4 -> 5 -> None`
2	`2`	`3`	`2 -> 1`	`2 -> 1 -> None`	`3 -> 4 -> 5 -> None`
3	`3`	`4`	`3 -> 2`	`3 -> 2 -> 1 -> None`	`4 -> 5 -> None`
4	`4`	`5`	`4 -> 3`	`4 -> 3 -> 2 -> 1 -> None`	`5 -> None`
5	`5`	`None`	`5 -> 4`	`5 -> 4 -> 3 -> 2 -> 1 -> None`	empty (`curr` is `None`)
End				return `prev`: `[5,4,3,2,1]`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Only the direction of each `next` pointer changes: no node moves and no value is copied, so one forward walk can flip the links one at a time.
2	Keep two lists apart: `prev` heads the nodes already reversed (empty at first) and `curr` heads the nodes not touched yet; each step moves `curr` to the front of `prev`'s list.
3	`prev, curr = None, head`; `while curr:` save `nxt = curr.next`, flip `curr.next = prev`, then `prev = curr` and `curr = nxt`; after the loop `return prev`.
4	The trap: `nxt = curr.next` must run before `curr.next = prev`. The flip overwrites the only link to the rest of the list, so flipping first loses every node after `curr`.

Target: Reverse Linked List (LeetCode 206). The old head becomes the new tail, so the first link the loop writes must point at None: prev starts as that None.

Boundary Model: Converging Boundaries [left, right] / Sliding Window [L, R]

Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.

Loop Invariant Termination

while (left < right) for converging pointers; while (right < n) with inner window shrink.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

A singly linked list is a chain of nodes where each node knows only the node after it (next). To reverse it you don't move any node and you don't copy any value: you make every next point to the node that used to come before it. The list can only be walked forward, so you do it in one forward walk, carrying two pointers: prev, the head of the part already reversed, and curr, the first node not touched yet.

🏟️ The Analogy: Turning Around a Line of People Holding Shoulders

Picture a queue where everyone rests a hand on the shoulder of the person in front. To turn the whole line around, you go from the front to the back and ask each person to move their hand to the person behind them instead. Before someone lets go, you must note who they were holding, or you lose track of the rest of the line. That note is nxt.

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

prev, curr = None, head
while curr:
    nxt = curr.next     # 1. remember the rest
    curr.next = prev    # 2. flip one link
    prev = curr         # 3. the reversed part grows
    curr = nxt          # 4. walk into the rest
return prev

Before every loop test, the nodes split into two separate lists: the reversed part starting at prev and the untouched part starting at curr. Each step moves exactly one node from the front of the untouched part to the front of the reversed part. The order of the four lines is the whole trick: curr.next = prev destroys the only link to the rest of the list, so nxt = curr.next must come first.

💡 Summary

Walk once, save next, flip it, step forward: when curr falls off the end, prev is the new head. The same four lines reverse any stretch of a list, which is how Reverse Linked List II and the palindrome check reuse them.

Flipping before saving: nxt = curr.next must run before curr.next = prev. The flip overwrites the only link to the rest of the list, so flipping first loses every node after curr: [1,2,3] comes back as [1].
Returning the wrong node: return prev, not head or curr. When the loop ends curr is None, and the old head is now the tail, pointing at None.
Stopping one node early: loop while curr:, not while curr.next:. The shorter loop never flips the last node, and the empty list (head is None) crashes on None.next.
Starting prev at head: start with prev = None. The old head becomes the tail and must end pointing at None; starting from head without clearing head.next leaves the first two nodes pointing at each other, a cycle.
Copying instead of rewiring: reading the values into a Python list and building new nodes gives the right values but uses O(N) extra memory; the four-line loop reuses the original nodes with O(1) extra space.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer turns "reverse the list" into one forward walk, and why the order of four lines is the whole answer.

Pattern Recognition Signals

The 10-second spot

"Reverse the list" and "return the reversed list": the nodes stay the same and only their order changes, and a singly linked list can only be walked forward. The need is to point every next the other way during one forward walk, in place: the Linked List Reversal tool.

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Before each loop test, prev is the head of the nodes already reversed and curr is the head of the nodes not touched yet, and every node is in exactly one of the two lists. Each step moves one node, curr, from the front of the untouched part to the front of the reversed part.

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

nxt = curr.next before curr.next = prev: the flip overwrites the only link to the rest of the list, so flipping first loses every node after curr.
return prev, not head or curr: when the loop ends curr is None, and the old head is now the tail, pointing at None.
while curr:, not while curr.next:: stopping one node early never flips the last node, and the empty list (head is None) crashes on None.next.
prev = None, not prev = head: the old head becomes the tail and must end pointing at None; starting from head without clearing head.next leaves a cycle between the first two nodes.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Linked List Reversal. The nodes stay where they are; only each next pointer has to point the other way, so I walk the list once with two pointers. prev is the head of the part I've already reversed, starting as None, and curr is the first node I haven't touched. At each step I save curr.next in nxt, point curr.next back at prev, then move prev to curr and curr to nxt. Every node moves from the untouched part to the front of the reversed part exactly once, so when curr runs off the end, prev is the new head. The trap is the order of those lines: if I flip before saving nxt, I lose the rest of the list. That's O(N) time and O(1) extra space, and no node is created.

So: prev heads the reversed part, curr the untouched part; save nxt before the flip, and return prev when curr is None.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

Look at the code: prev = None and curr = head run once. while curr: runs once per node, because each pass ends with curr = nxt, which moves curr one node forward, and the loop stops when curr is None. Inside, nxt = curr.next, curr.next = prev, prev = curr and curr = nxt are four assignments, O(1). N nodes times O(1) work is O(N), and return prev is O(1).

SPACE COMPLEXITY

O(1)

The code creates no node and no list: it only rewrites the next field that every node already has. The extra memory is three pointers, prev, curr and nxt, whatever the length of the list, so O(1). The returned list is the input's own nodes, so there is no separate output to count.

Formal Recurrence Relation

T = O(1) setup + N · O(1) per node = O(N)

Derivation Progression

Set up

O(1)

prev = None and curr = head run once.

Visit every node

N iterations

Each pass of while curr: ends with curr = nxt, one node forward, so the loop body runs exactly once per node.

Flip one link

O(1) per node

nxt = curr.next, curr.next = prev, prev = curr, curr = nxt: four pointer assignments, no inner loop.

Total

O(N)

N iterations of constant work, plus the O(1) return prev.

Variable Definitions

$N$

Number of nodes in the list (0 to 5000)

$prev$

Head of the part already reversed (None at the start)

$curr$

First node not flipped yet (None once every node is done)

$nxt$

curr.next, saved before the flip overwrites it

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion (a recursive version would use an O(N) call stack)

🔵 Auxiliary Heap

O(1): three pointers, prev, curr and nxt; no node is created

🟢 Output Space

None extra: the returned list is the input's own nodes, rewired

Boundary Best / Worst Cases

Best Case

$O(1)$ : an empty list never enters the loop

Average Case

$O(N)$

Worst Case

$O(N)$ : every node is visited once

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

Triggers: "reverse the list", "return the reversed list". The nodes stay the same and only the order of the links changes, and a singly linked list can only be walked forward: Linked List Reversal, flipping each next during one walk.

CONSTRAINTS & BOUNDS

$0 \le N \le 5000$ nodes, values in $[-5000, 5000]$ . Any $O(N)$ approach fits; the point is memory: copying the values costs $O(N)$ extra, rewiring in place costs $O(1)$ . A recursive version is also $O(N)$ time but puts $N$ frames on the call stack.

FAANG PRODUCTION TRAPS & EDGE CASES

nxt = curr.next must run before curr.next = prev, or the rest of the list is lost. At scale: a recursive reversal of a long list can overflow the call stack, which the loop never does, and if other threads can read the list while it is being reversed, they may see a half-flipped chain; reverse a private list, or publish the new head only after the loop ends.

Core Algorithmic State Invariants

1. Two Lists That Never Mix

Before each loop test, `prev` heads the nodes already reversed and `curr` heads the nodes not touched yet; every node is in exactly one of them, and each step moves `curr` to the front of `prev`'s list.

2. Save Before You Flip

`curr.next = prev` overwrites the only link to the rest of the list, so `nxt = curr.next` must run first; flipping first loses every node after `curr`.

3. One Pass, No New Nodes

Each node is visited once and gets four pointer assignments, and only `prev`, `curr` and `nxt` are extra: O(N) time and O(1) space, and `prev` is the new head when `curr` becomes `None`.

Theory Context•Two Pointers & Sliding Window

EasyLC 206

Reverse Linked List (LeetCode 206)

You will see how one forward walk with prev, curr and a saved nxt turns every link of a list around without copying a node.

Target Frequency:AmazonAppleGoogleMetaMicrosoft

You get head, the first node of a singly linked list. Each node holds a value val and a pointer next to the node after it; the last node's next is None, and an empty list has head = None.

Follow-up: once you have one version, write the other one too, a loop and a recursive function.

Worked Examples

Example 1

Input:head = [1,2,3,4,5]

Output:[5,4,3,2,1]

Explanation: Every link now points the other way, so `5`, the old last node, is the new head and `1` ends the list.

Example 2

Input:head = [1,2]

Output:[2,1]

Explanation: `2` now points to `1`, and `1` points to `None`.

Example 3

Input:head = []

Output:[]

Explanation: An empty list has nothing to turn around, so the answer is the empty list.

⚖️Formal Constraints & Bounds

The number of nodes in the list is in the range [0, 5000].
-5000 <= Node.val <= 5000

Deep-Dive & Conceptual Insights

Why It Works & Core Invariant

Real-World Scenario & Production Applications

Step-by-Step Execution Trace Table

Input head = [1,2,3,4,5] (LeetCode Example 1). Before each step, prev heads the reversed part and curr heads the untouched part:

Step	`curr`	`nxt = curr.next`	`curr.next = prev`	Reversed part (from `prev`) after the step	Untouched part (from `curr`) after the step
1	`1`	`2`	`1 -> None`	`1 -> None`	`2 -> 3 -> 4 -> 5 -> None`
2	`2`	`3`	`2 -> 1`	`2 -> 1 -> None`	`3 -> 4 -> 5 -> None`
3	`3`	`4`	`3 -> 2`	`3 -> 2 -> 1 -> None`	`4 -> 5 -> None`
4	`4`	`5`	`4 -> 3`	`4 -> 3 -> 2 -> 1 -> None`	`5 -> None`
5	`5`	`None`	`5 -> 4`	`5 -> 4 -> 3 -> 2 -> 1 -> None`	empty (`curr` is `None`)
End				return `prev`: `[5,4,3,2,1]`

Scroll horizontally to see all columns, or expand to full screen

Core Invariant Specification & Code Shape

Archetype Code Shape

Python

1	Only the direction of each `next` pointer changes: no node moves and no value is copied, so one forward walk can flip the links one at a time.
2	Keep two lists apart: `prev` heads the nodes already reversed (empty at first) and `curr` heads the nodes not touched yet; each step moves `curr` to the front of `prev`'s list.
3	`prev, curr = None, head`; `while curr:` save `nxt = curr.next`, flip `curr.next = prev`, then `prev = curr` and `curr = nxt`; after the loop `return prev`.
4	The trap: `nxt = curr.next` must run before `curr.next = prev`. The flip overwrites the only link to the rest of the list, so flipping first loses every node after `curr`.

Target: Reverse Linked List (LeetCode 206). The old head becomes the new tail, so the first link the loop writes must point at None: prev starts as that None.

Boundary Model: Converging Boundaries [left, right] / Sliding Window [L, R]

Indices step monotonically inward or rightward. Each step permanently eliminates an entire row, column, or infeasible candidate window.

Loop Invariant Termination

while (left < right) for converging pointers; while (right < n) with inner window shrink.

Conceptual Narrative

🧭 Conceptual Foundation & Pattern Intuition

🏟️ The Analogy: Turning Around a Line of People Holding Shoulders

🪄 The Mathematical Harmony / Magic Trick

Code / Blueprint

prev, curr = None, head
while curr:
    nxt = curr.next     # 1. remember the rest
    curr.next = prev    # 2. flip one link
    prev = curr         # 3. the reversed part grows
    curr = nxt          # 4. walk into the rest
return prev

💡 Summary

Flipping before saving: nxt = curr.next must run before curr.next = prev. The flip overwrites the only link to the rest of the list, so flipping first loses every node after curr: [1,2,3] comes back as [1].
Returning the wrong node: return prev, not head or curr. When the loop ends curr is None, and the old head is now the tail, pointing at None.
Stopping one node early: loop while curr:, not while curr.next:. The shorter loop never flips the last node, and the empty list (head is None) crashes on None.next.
Starting prev at head: start with prev = None. The old head becomes the tail and must end pointing at None; starting from head without clearing head.next leaves the first two nodes pointing at each other, a cycle.
Copying instead of rewiring: reading the values into a Python list and building new nodes gives the right values but uses O(N) extra memory; the four-line loop reuses the original nodes with O(1) extra space.

Senior SWE Reasoning Architecture

4-Phase Thought Process Model

You will see how a senior engineer turns "reverse the list" into one forward walk, and why the order of four lines is the whole answer.

Pattern Recognition Signals

The 10-second spot

Formulating the Predicate & Invariants

Turning intuition into a boolean rule

Silent Failure Traps & Edge Cases

Where confident candidates still lose points

nxt = curr.next before curr.next = prev: the flip overwrites the only link to the rest of the list, so flipping first loses every node after curr.
return prev, not head or curr: when the loop ends curr is None, and the old head is now the tail, pointing at None.
while curr:, not while curr.next:: stopping one node early never flips the last node, and the empty list (head is None) crashes on None.next.
prev = None, not prev = head: the old head becomes the tail and must end pointing at None; starting from head without clearing head.next leaves a cycle between the first two nodes.

The 60-Second Interview Pitch

Say this out loud before you type a single line

I'd use Linked List Reversal. The nodes stay where they are; only each next pointer has to point the other way, so I walk the list once with two pointers. prev is the head of the part I've already reversed, starting as None, and curr is the first node I haven't touched. At each step I save curr.next in nxt, point curr.next back at prev, then move prev to curr and curr to nxt. Every node moves from the untouched part to the front of the reversed part exactly once, so when curr runs off the end, prev is the new head. The trap is the order of those lines: if I flip before saving nxt, I lose the rest of the list. That's O(N) time and O(1) extra space, and no node is created.

So: prev heads the reversed part, curr the untouched part; save nxt before the flip, and return prev when curr is None.

Big-O Invariant Derivation

Complexity & Mathematical Proof

TIME COMPLEXITY

O(N)

SPACE COMPLEXITY

O(1)

Formal Recurrence Relation

T = O(1) setup + N · O(1) per node = O(N)

Derivation Progression

Set up

O(1)

prev = None and curr = head run once.

Visit every node

N iterations

Each pass of while curr: ends with curr = nxt, one node forward, so the loop body runs exactly once per node.

Flip one link

O(1) per node

nxt = curr.next, curr.next = prev, prev = curr, curr = nxt: four pointer assignments, no inner loop.

Total

O(N)

N iterations of constant work, plus the O(1) return prev.

Variable Definitions

$N$

Number of nodes in the list (0 to 5000)

$prev$

Head of the part already reversed (None at the start)

$curr$

First node not flipped yet (None once every node is done)

$nxt$

curr.next, saved before the flip overwrites it

Memory Architecture & Bounds

🟣 Call Stack

O(1) Iterative, no recursion (a recursive version would use an O(N) call stack)

🔵 Auxiliary Heap

O(1): three pointers, prev, curr and nxt; no node is created

🟢 Output Space

None extra: the returned list is the input's own nodes, rewired

Boundary Best / Worst Cases

Best Case

$O(1)$ : an empty list never enters the loop

Average Case

$O(N)$

Worst Case

$O(N)$ : every node is visited once

Pointer Invariant Transition Progression

Synthesizing vector architecture diagram...

Staff+ Engineering Perspective

Senior SWE Deconstruction & Hardware Caveats

ARCHITECTURAL SIGNALS & INTERVIEW TRIGGERS

CONSTRAINTS & BOUNDS

FAANG PRODUCTION TRAPS & EDGE CASES

Core Algorithmic State Invariants

1. Two Lists That Never Mix

2. Save Before You Flip

`curr.next = prev` overwrites the only link to the rest of the list, so `nxt = curr.next` must run first; flipping first loses every node after `curr`.

3. One Pass, No New Nodes

Each node is visited once and gets four pointer assignments, and only `prev`, `curr` and `nxt` are extra: O(N) time and O(1) space, and `prev` is the new head when `curr` becomes `None`.

Rosetta Dual-Monaco Comparison

Python 3

CANONICAL INVARIANT TEMPLATE

CONCRETE: REVERSE LINKED LIST (LEETCODE 206)

T = O(N)S = O(1)

Pattern Implementation Mapping TableCanonical Invariant ⟷ Concrete Code ⟷ Engineering Rationale

Canonical Invariant	Concrete Code	Engineering Rationale
Start with an empty reversed part	`prev = None`	The old head becomes the new tail, so the first link the loop writes must point at None: prev starts as that None.
Start at the first node that is not flipped yet	`curr = head`	Every node from curr onward still has its original next pointer; nothing has been touched.
Visit every node exactly once	`while curr:`	The loop stops when curr falls off the end, so the last node is flipped too, and an empty list (head is None) never enters the loop.
Save the rest of the list before touching the link	`nxt = curr.next`	curr.next is the only way to reach the untouched rest; the next line overwrites it, so it must be saved first.
Flip one link	`curr.next = prev`	curr now points back at the reversed part instead of forward.
Grow the reversed part and step into the rest	`prev = curr curr = nxt`	curr joins the front of the reversed part, and the walk continues from the saved nxt.
The last node flipped is the new head	`return prev`	When curr is None, prev is the old tail, which now heads the whole reversed list.

Step

curr

nxt = curr.next

curr.next = prev

Reversed part (from prev) after the step

Untouched part (from curr) after the step

1

2

1 -> None

2 -> 3 -> 4 -> 5 -> None

2

3

2 -> 1

2 -> 1 -> None

3 -> 4 -> 5 -> None

3

4

3 -> 2

3 -> 2 -> 1 -> None

4 -> 5 -> None

4

5

4 -> 3

4 -> 3 -> 2 -> 1 -> None

5 -> None

5

None

5 -> 4

5 -> 4 -> 3 -> 2 -> 1 -> None

empty (curr is None)

End

return prev: [5,4,3,2,1]

prev, curr = None, head while curr: nxt = curr.next # 1. remember the rest curr.next = prev # 2. flip one link prev = curr # 3. the reversed part grows curr = nxt # 4. walk into the rest return prev

Step

curr

nxt = curr.next

curr.next = prev

Reversed part (from prev) after the step

Untouched part (from curr) after the step

1

2

1 -> None

2 -> 3 -> 4 -> 5 -> None

2

3

2 -> 1

2 -> 1 -> None

3 -> 4 -> 5 -> None

3

4

3 -> 2

3 -> 2 -> 1 -> None

4 -> 5 -> None

4

5

4 -> 3

4 -> 3 -> 2 -> 1 -> None

5 -> None

5

None

5 -> 4

5 -> 4 -> 3 -> 2 -> 1 -> None

empty (curr is None)

End

return prev: [5,4,3,2,1]

Canonical Invariant

Concrete Code

Engineering Rationale

Start with an empty reversed part

prev = None

The old head becomes the new tail, so the first link the loop writes must point at None: prev starts as that None.

Start at the first node that is not flipped yet

curr = head

Every node from curr onward still has its original next pointer; nothing has been touched.

Visit every node exactly once

while curr:

The loop stops when curr falls off the end, so the last node is flipped too, and an empty list (head is None) never enters the loop.

Save the rest of the list before touching the link

nxt = curr.next

curr.next is the only way to reach the untouched rest; the next line overwrites it, so it must be saved first.

Flip one link

curr.next = prev

curr now points back at the reversed part instead of forward.

Grow the reversed part and step into the rest

prev = curr
curr = nxt

curr joins the front of the reversed part, and the walk continues from the saved nxt.

The last node flipped is the new head

return prev

When curr is None, prev is the old tail, which now heads the whole reversed list.