Middle of the Linked List (LeetCode 876)
You're handed the head of a singly linked list. Return the node sitting in the middle of that list.
When the list has two middle nodes (an even length), return the second of the two.
Worked Examples
head = [1,2,3,4,5][3,4,5]head = [1,2,3,4,5,6][4,5,6]⚖️Formal Constraints & Bounds
The number of nodes in the list is in the range
[1, 100].1 <= Node.val <= 100
Core Insight
The 2:1 speed ratio ensures single-pass midpoint location without calculating total length beforehand.
Real-World Scenario & Production Applications
Linked list merge sort partition phase, finding median elements in streaming lists, and audio playlist shuffling.
Step-by-Step Execution Trace Table
| Iteration | slow Node | fast Node | Remaining fast.next |
|---|---|---|---|
| Init | Node 1 | Node 1 | Has next |
| 1 | Node 2 | Node 3 | Has next |
| 2 | Node 3 | Node 5 | fast.next is None → Stop! Return Node 3 |
| 1 | slow = head |
| 2 | fast = head |
| 3 | while fast and fast.next: |
| 4 | slow = slow.next |
| 5 | fast = fast.next.next |
| 6 | return slow |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This is the first archetype in the pattern where the two pointers move at different speeds instead of just different starting positions — a genuinely new mechanism.
🐢🐇 The Analogy: A Runner and a Walker on the Same Track
Imagine a walker and a runner starting at the same point on a straight track, with the runner moving exactly twice as fast. By the time the runner reaches the finish line, the walker — moving at half the speed — has covered exactly half the distance. No measuring tape required: the walker's position is the midpoint, purely because of the 2:1 speed ratio.
🔑 The Key Idea in the Code
There's no length-counting pass beforehand — the moment fast (which has covered twice the ground) runs out of track, slow is guaranteed to be sitting at the halfway point, by the same logic as the runner and walker.
Null pointer dereference on odd vs even lists:
while fast and fast.next:is mandatory. Checking onlywhile fast:causesfast.next.nextto crash with AttributeError on the boundary.Off-by-one during half comparison: On odd-length lists, the middle node belongs to the reversed half; comparing
while p2:(the reversed second half) terminates cleanly for both odd and even lengths without index mismatch.Auxiliary space leakage: Copying node values into a Python list
vals = []incurs space and violates the space follow-up requirement.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Linked list midpoint search or merge-sort split without knowing length in advance.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: distance(head, slow) == floor(distance(head, fast) / 2).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use two pointers starting at head. Slow moves 1 step, fast moves 2 steps. When fast or fast.next is null, slow is at the middle node. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Fast pointer advances 2 steps while slow advances 1 step. When fast reaches end in N/2 iterations, slow is at middle.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only two Node pointer references (slow, fast) are maintained in memory.
T(N) = ⌈ N/2 ⌉ iterations = O(N)
Derivation Progression
fast_speed = 2 × slow_speed
Fast pointer traverses 2 nodes per cycle while slow pointer traverses 1.
⌊ N/2 ⌋ loop iterations
When fast reaches None or fast.next is None, slow has traveled exactly floor(N/2) nodes.
N node visits = O(N)
Total pointer hops equal N.
Variable Definitions
Total number of nodes in the linked list
Memory Architecture & Bounds
O(1) Iterative
O(1) Two node references
O(1) Reference to middle node
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "middle of singly linked list", "if two middle nodes, return second middle node". Floyd's Tortoise and Hare speed differential pattern ( vs ).
Number of nodes . Single pass time with pointer space.
Null pointer exception when advancing fast.next.next (loop condition must explicitly require while fast and fast.next). For even , fast lands on None, and slow lands on the second middle node as requested.
Middle of the Linked List (LeetCode 876)
You're handed the head of a singly linked list. Return the node sitting in the middle of that list.
When the list has two middle nodes (an even length), return the second of the two.
Worked Examples
head = [1,2,3,4,5][3,4,5]head = [1,2,3,4,5,6][4,5,6]⚖️Formal Constraints & Bounds
The number of nodes in the list is in the range
[1, 100].1 <= Node.val <= 100
Core Insight
The 2:1 speed ratio ensures single-pass midpoint location without calculating total length beforehand.
Real-World Scenario & Production Applications
Linked list merge sort partition phase, finding median elements in streaming lists, and audio playlist shuffling.
Step-by-Step Execution Trace Table
| Iteration | slow Node | fast Node | Remaining fast.next |
|---|---|---|---|
| Init | Node 1 | Node 1 | Has next |
| 1 | Node 2 | Node 3 | Has next |
| 2 | Node 3 | Node 5 | fast.next is None → Stop! Return Node 3 |
| 1 | slow = head |
| 2 | fast = head |
| 3 | while fast and fast.next: |
| 4 | slow = slow.next |
| 5 | fast = fast.next.next |
| 6 | return slow |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
This is the first archetype in the pattern where the two pointers move at different speeds instead of just different starting positions — a genuinely new mechanism.
🐢🐇 The Analogy: A Runner and a Walker on the Same Track
Imagine a walker and a runner starting at the same point on a straight track, with the runner moving exactly twice as fast. By the time the runner reaches the finish line, the walker — moving at half the speed — has covered exactly half the distance. No measuring tape required: the walker's position is the midpoint, purely because of the 2:1 speed ratio.
🔑 The Key Idea in the Code
There's no length-counting pass beforehand — the moment fast (which has covered twice the ground) runs out of track, slow is guaranteed to be sitting at the halfway point, by the same logic as the runner and walker.
Null pointer dereference on odd vs even lists:
while fast and fast.next:is mandatory. Checking onlywhile fast:causesfast.next.nextto crash with AttributeError on the boundary.Off-by-one during half comparison: On odd-length lists, the middle node belongs to the reversed half; comparing
while p2:(the reversed second half) terminates cleanly for both odd and even lengths without index mismatch.Auxiliary space leakage: Copying node values into a Python list
vals = []incurs space and violates the space follow-up requirement.
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Linked list midpoint search or merge-sort split without knowing length in advance.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: distance(head, slow) == floor(distance(head, fast) / 2).
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
This problem's traps are in Common Pitfalls above.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I use two pointers starting at head. Slow moves 1 step, fast moves 2 steps. When fast or fast.next is null, slow is at the middle node. Runs in
O(N)time andO(1)space."
Complexity & Mathematical Proof
O(N)
Look at the execution steps: Fast pointer advances 2 steps while slow advances 1 step. When fast reaches end in N/2 iterations, slow is at middle.
O(1) Auxiliary
Look at memory allocations: Call stack uses O(1) Iterative. Only two Node pointer references (slow, fast) are maintained in memory.
T(N) = ⌈ N/2 ⌉ iterations = O(N)
Derivation Progression
fast_speed = 2 × slow_speed
Fast pointer traverses 2 nodes per cycle while slow pointer traverses 1.
⌊ N/2 ⌋ loop iterations
When fast reaches None or fast.next is None, slow has traveled exactly floor(N/2) nodes.
N node visits = O(N)
Total pointer hops equal N.
Variable Definitions
Total number of nodes in the linked list
Memory Architecture & Bounds
O(1) Iterative
O(1) Two node references
O(1) Reference to middle node
Boundary Best / Worst Cases
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "middle of singly linked list", "if two middle nodes, return second middle node". Floyd's Tortoise and Hare speed differential pattern ( vs ).
Number of nodes . Single pass time with pointer space.
Null pointer exception when advancing fast.next.next (loop condition must explicitly require while fast and fast.next). For even , fast lands on None, and slow lands on the second middle node as requested.