73. Middle of the Linked List
🔗 LeetCode Problem: 876. Middle of the Linked List
📊 Difficulty: Easy
🏷️ Topics: Linked List, Two Pointers
Problem Statement
Given the head of a singly linked list, return the middle node of the linked list.
If there are two middle nodes, return the second middle node.
Example 1:
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
Visual:
1 -> 2 -> 3 -> 4 -> 5 -> null
↑
Middle
Example 2:
Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes with values 3 and 4, we return the second one.
Visual:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
↑
Middle (second)
Constraints:
- The number of nodes in the list is in the range [1, 100].
- 1 <= Node.val <= 100
🎨 Visual Understanding
The Problem Visualized
Example 1: Odd length (5 nodes)
List: 1 -> 2 -> 3 -> 4 -> 5 -> null
0 1 2 3 4
Total nodes: 5
Middle index: 5 / 2 = 2
Middle node: 3 ✓
Example 2: Even length (6 nodes)
List: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
0 1 2 3 4 5
Total nodes: 6
Two middles: index 2 (value 3) and index 3 (value 4)
Return: Second middle (index 3, value 4) ✓
How to find middle in one pass?
Approach 1 (Two passes):
Pass 1: Count total nodes = n
Pass 2: Move to index n/2
Approach 2 (One pass):
Use Fast & Slow pointers! 🐢🐇
When fast reaches end:
Slow is at middle! ✓
🚨 CRITICAL INSIGHT - Fast & Slow for Middle!
The Key Pattern!
Use two pointers moving at different speeds:
- Slow: moves 1 step at a time
- Fast: moves 2 steps at a time
When fast reaches the end:
Slow has traveled half the distance
Slow is at the MIDDLE! ✓
Why does this work?
Fast moves 2x faster than slow
When fast travels n steps (reaches end)
Slow travels n/2 steps (at middle)
Visual proof:
Odd (5 nodes):
slow: 0 -> 1 -> 2 (middle)
fast: 0 -> 2 -> 4 -> null
Even (6 nodes):
slow: 0 -> 1 -> 2 -> 3 (second middle)
fast: 0 -> 2 -> 4 -> null
Visual Trace - Step by Step
Odd length: 1 -> 2 -> 3 -> 4 -> 5 -> null
Initial:
slow: 1
fast: 1
Step 1:
slow: 1 -> 2
fast: 1 -> 2 -> 3
Step 2:
slow: 2 -> 3
fast: 3 -> 4 -> 5
Step 3:
slow: 3 -> 4
fast: 5 -> null (fast.next = null, stop!)
Return slow (node 3) ✓
Even length: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Initial:
slow: 1
fast: 1
Step 1:
slow: 1 -> 2
fast: 1 -> 2 -> 3
Step 2:
slow: 2 -> 3
fast: 3 -> 4 -> 5
Step 3:
slow: 3 -> 4
fast: 5 -> 6 -> null
Step 4:
slow: 4 -> 5
fast: null (fast = null, stop!)
Return slow (node 4, second middle) ✓
Why This Returns Second Middle for Even
Loop condition: while (fast != null && fast.next != null)
For even length:
Fast eventually becomes null (goes past the end)
Slow ends at second middle
Example: [1, 2, 3, 4]
Position: 0 1 2 3
slow moves: 0 -> 1 -> 2
fast moves: 0 -> 2 -> null
Slow at index 2 (second middle) ✓
If we want FIRST middle for even:
Use: while (fast.next != null && fast.next.next != null)
Fast stops one step earlier
Slow ends at first middle
🎯 Approach 1: Two Pass (Count then Move)
The Most Natural Thinking 💭
Core Logic:
Pass 1: Count total nodes
Pass 2: Move to index n/2
Implementation
/**
* Two-pass approach
* Time: O(n), Space: O(1)
*/
public ListNode middleNode(ListNode head) {
// First pass: count nodes
int count = 0;
ListNode current = head;
while (current != null) {
count++;
current = current.next;
}
// Find middle index
int middleIndex = count / 2;
// Second pass: move to middle
current = head;
for (int i = 0; i < middleIndex; i++) {
current = current.next;
}
return current;
}
⏰ Time: O(n) - Two passes through list
💾 Space: O(1) - Only variables
✓ Works, but requires two passes!
🎯 Approach 2: Fast & Slow Pointers (Optimal) ⭐
Better Approach 💡
🧠 The Core Insight
Use two pointers at different speeds!
When fast (2x speed) reaches end:
Slow (1x speed) is at middle!
One pass solution! ✓
The Strategy:
Fast & Slow Pointers:
1. Initialize both at head
2. Move slow 1 step, fast 2 steps
3. When fast reaches end, stop
4. Return slow (it's at middle!)
Time: O(n) - Single pass
Space: O(1) - Two pointers
Implementation
/**
* Fast & Slow Pointers - One Pass
* Time: O(n), Space: O(1)
*/
public ListNode middleNode(ListNode head) {
ListNode slow = head; // Tortoise 🐢
ListNode fast = head; // Hare 🐇
// Move until fast reaches end
while (fast != null && fast.next != null) {
slow = slow.next; // Move 1 step
fast = fast.next.next; // Move 2 steps
}
// Slow is at middle!
return slow;
}
⏰ Time: O(n) - Single pass through list
💾 Space: O(1) - Only two pointers
🔍 Dry Run
Example 1: Odd length [1,2,3,4,5]
Goal: Find middle node
Initial:
slow = 1
fast = 1
Check: fast != null? Yes, fast.next != null? Yes
Iteration 1:
slow = slow.next = 2
fast = fast.next.next = 3
Current positions:
slow: 2
fast: 3
Check: fast != null? Yes, fast.next != null? Yes
Iteration 2:
slow = slow.next = 3
fast = fast.next.next = 5
Current positions:
slow: 3
fast: 5
Check: fast != null? Yes, fast.next != null? No!
Loop ends
Return slow (node 3) ✓
Visual:
1 -> 2 -> 3 -> 4 -> 5 -> null
↑ ↑
slow fast
Example 2: Even length [1,2,3,4,5,6]
Goal: Find second middle node
Initial:
slow = 1
fast = 1
Iteration 1:
slow = 2
fast = 3
Check: Continue
Iteration 2:
slow = 3
fast = 5
Check: Continue
Iteration 3:
slow = 4
fast = fast.next.next = null (5 -> 6 -> null)
Current positions:
slow: 4
fast: null
Check: fast != null? No!
Loop ends
Return slow (node 4, second middle) ✓
Visual:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
↑ ↑
slow fast
Example 3: Single node [1]
Initial:
slow = 1
fast = 1
Check: fast != null? Yes, fast.next != null? No!
Loop doesn't execute
Return slow (node 1) ✓
Example 4: Two nodes [1,2]
Initial:
slow = 1
fast = 1
Check: fast != null? Yes, fast.next != null? Yes
Iteration 1:
slow = 2
fast = fast.next.next = null (1 -> 2 -> null)
Check: fast != null? No!
Loop ends
Return slow (node 2, second middle) ✓
🎯 Why This Works - Deep Dive
The Speed Ratio:
═══════════════════════════════════════════════════════════════
Key insight: Fast moves 2x speed of slow
Distance ratio:
When fast travels 2n steps
Slow travels n steps
For list of length L:
When fast reaches end (position L)
Slow is at position L/2
L/2 is the MIDDLE! ✓
Mathematical Proof (Odd length):
═══════════════════════════════════════════════════════════════
List length: 2k + 1 (odd)
Middle index: k
Fast pointer stops when:
fast.next = null
This happens when fast is at last node (index 2k)
Number of iterations: k
Each iteration: slow moves 1, fast moves 2
After k iterations:
Slow at index k (middle!) ✓
Fast at index 2k (last node)
Example: Length 5 (k = 2)
Middle: index 2
Iterations: 2
Slow: 0 -> 1 -> 2 ✓
Fast: 0 -> 2 -> 4
Mathematical Proof (Even length):
═══════════════════════════════════════════════════════════════
List length: 2k (even)
Second middle index: k
Fast pointer stops when:
fast = null
This happens after fast goes past last node
Number of iterations: k
After k iterations:
Slow at index k (second middle!) ✓
Fast went past the end (null)
Example: Length 6 (k = 3)
Second middle: index 3
Iterations: 3
Slow: 0 -> 1 -> 2 -> 3 ✓
Fast: 0 -> 2 -> 4 -> null
The Loop Condition:
═══════════════════════════════════════════════════════════════
while (fast != null && fast.next != null)
Why both checks?
fast != null: Fast hasn't gone past end
fast.next != null: Can move one more step
Together: Safe to do fast.next.next
For ODD length:
Loop ends when: fast.next = null
Fast is at last node
Slow is at middle ✓
For EVEN length:
Loop ends when: fast = null
Fast went past end
Slow is at second middle ✓
Why Second Middle for Even?
═══════════════════════════════════════════════════════════════
The loop condition naturally gives second middle!
For [1, 2, 3, 4]:
Iteration 1: slow=2, fast=3
Iteration 2: slow=3, fast=null
Slow ends at index 2 (value 3)
This is the SECOND middle (indices 1 and 2)
To get FIRST middle:
Change condition:
while (fast.next != null && fast.next.next != null)
Fast stops one iteration earlier
Slow ends at first middle
Time Complexity:
═══════════════════════════════════════════════════════════════
Single pass through list:
Fast pointer moves 2 steps per iteration
Reaches end in n/2 iterations
Time: O(n/2) = O(n) ✓
Space: O(1) - Only two pointers
Variant: First Middle for Even Length
/**
* Return FIRST middle for even length
*/
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
// Different condition: stop one step earlier
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow; // First middle for even
}
Example: [1,2,3,4]
Iteration 1:
slow = 2
fast = 3
Check: fast.next (4) != null? Yes
fast.next.next (null) != null? No!
Loop ends
Return slow (node 2, first middle) ✓
⚠️ Common Mistakes to Avoid
Mistake 1: Wrong loop condition
// ❌ WRONG - Can throw NullPointerException
while (fast != null) {
fast = fast.next.next; // What if fast.next is null?
}
// ✓ CORRECT - Check both
while (fast != null && fast.next != null) {
fast = fast.next.next;
}
Mistake 2: Not starting both at head
// ❌ WRONG - Fast starts ahead
ListNode slow = head;
ListNode fast = head.next;
// ✓ CORRECT - Both start at head
ListNode slow = head;
ListNode fast = head;
Mistake 3: Moving wrong distances
// ❌ WRONG - Both move same distance
slow = slow.next;
fast = fast.next; // Should be fast.next.next!
// ✓ CORRECT - Different speeds
slow = slow.next; // 1 step
fast = fast.next.next; // 2 steps
Mistake 4: Forgetting edge cases
// ❌ WRONG - No null check
public ListNode middleNode(ListNode head) {
// What if head is null?
}
// ✓ CORRECT - Though problem guarantees non-empty
// The algorithm handles single node correctly anyway
if (head == null) return null;
Mistake 5: Returning wrong node
// ❌ WRONG - Returns fast
return fast; // Fast is at end, not middle!
// ✓ CORRECT - Returns slow
return slow; // Slow is at middle
🎯 Pattern Recognition
Problem Type: Find Middle of Linked List
Core Pattern: Fast & Slow Pointers
When to Apply:
✓ Find middle element
✓ Single pass requirement
✓ O(1) space requirement
✓ Can't count nodes first
✓ Linked list traversal
Recognition Keywords:
- "Middle node"
- "Middle element"
- "Center of list"
- "One pass" or "single traversal"
- "Without counting"
Similar Problems:
- Delete Middle Node (LC 2095) - Find then delete
- Reorder List (LC 143) - Find middle, split, reorder
- Palindrome Linked List (LC 234) - Find middle, reverse half
- Merge Sort Linked List - Find middle to split
Key Components:
┌────────────────────────────────────────────┐
│ 1. Two pointers: slow and fast │
│ 2. Speeds: 1x and 2x │
│ 3. Fast reaches end → slow at middle │
│ 4. O(n) time, O(1) space │
└────────────────────────────────────────────┘
This is a FUNDAMENTAL building block for many problems!
🧠 Interview Strategy
Step 1: "Find middle → Fast & slow pointers"
Step 2: "Fast moves 2x, slow moves 1x"
Step 3: "When fast reaches end, slow is at middle"
Step 4: "One pass, O(1) space"
Key Points to Mention:
- Two pointers at different speeds
- Slow: 1 step, Fast: 2 steps
- When fast reaches end, slow at middle
- For even length: returns second middle
- Loop: while (fast != null && fast.next != null)
- Single pass through list
- Time: O(n), Space: O(1)
- Alternative: Count then move (two passes)
Why This Approach?
"I'll use fast and slow pointers moving at different speeds.
The slow pointer moves one step while the fast pointer moves
two steps. When the fast pointer reaches the end, the slow
pointer will be at the middle since it traveled half the
distance. This gives me a one-pass solution with O(1) space."
Why Different Speeds?
"By having the fast pointer move twice as fast, when it covers
the entire list length, the slow pointer has covered exactly
half the distance, placing it at the middle."
Edge Cases to Mention:
✓ Single node (already at middle)
✓ Two nodes (second middle)
✓ Odd vs even length
✓ Fast reaching null vs fast.next reaching null
📝 Quick Revision Notes
🎯 Core Concept:
Middle of Linked List: Use fast & slow pointers 🐢🐇. Slow: 1 step, Fast: 2 steps. When fast reaches end, slow at middle! Loop: while (fast != null && fast.next != null). Even length: returns second middle. One pass, O(n) time, O(1) space!
⚡ Quick Implementation:
class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Test {
public ListNode middleNode(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
public static void main(String[] args) {
Test t = new Test();
ListNode head1 = new ListNode(1); // even number of nodes
head1.next = new ListNode(2);
head1.next.next = new ListNode(3);
head1.next.next.next = new ListNode(4);
head1.next.next.next.next = new ListNode(5);
head1.next.next.next.next.next = new ListNode(6);
System.out.println("head1: "+t.middleNode(head1).val); // 4
ListNode head2 = new ListNode(1); // even number of nodes
head2.next = new ListNode(2);
head2.next.next = new ListNode(3);
head2.next.next.next = new ListNode(4);
head2.next.next.next.next = new ListNode(5);
System.out.println("head2: "+t.middleNode(head2).val); // 3
}
}
🔑 Key Insights:
- Pattern: Fast & Slow Pointers for middle
- Slow: 1 step per iteration 🐢
- Fast: 2 steps per iteration 🐇
- End: Fast reaches end → slow at middle
- Odd: Fast.next = null, slow at middle
- Even: Fast = null, slow at second middle
- Loop: Check both fast and fast.next
- Single Pass: No counting needed
- Time: O(n), Space: O(1)
🎪 Memory Aid:
"Fast runs 2x, slow runs 1x. Fast finishes → slow at half!"
Think: "Race to end, slow wins middle position!" 🏁
💡 The Key Insight:
Speed ratio determines position ratio!
Fast: 2x speed
Slow: 1x speed
When fast travels full distance (n):
Slow travels half distance (n/2)
n/2 = MIDDLE! ✓
⚠️ Critical Details:
1. Both start at head
2. Slow: slow.next (1 step)
3. Fast: fast.next.next (2 steps)
4. Loop: fast != null AND fast.next != null
5. Why both? Fast moves 2 steps, need both valid
6. Odd: stops when fast.next = null
7. Even: stops when fast = null
8. Return: slow (it's at middle)
9. Even length: naturally gives second middle
🔥 The Loop Condition:
while (fast != null && fast.next != null)
└─────┬──────┘ └──────┬──────────┘
│ │
Fast exists One step ahead valid
Together: Safe for fast.next.next ✓
Odd length:
Ends when: fast.next = null
Fast at last node
Slow at middle ✓
Even length:
Ends when: fast = null
Fast went past end
Slow at second middle ✓
💡 Visual Proof:
List: 1 -> 2 -> 3 -> 4 -> 5
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3 (fast moved 2 positions)
Step 2: slow=3, fast=5 (fast at end!)
Slow moved 2 steps, fast moved 4 steps
Slow at position 2 (middle of 0-4) ✓
🎯 Variant for First Middle:
// For even length, return FIRST middle
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// Stops one iteration earlier
// [1,2,3,4]: returns 2 (first middle)
🧪 Edge Cases
Case 1: Single node
Input: head = [1]
Output: [1]
(Only one node, it's the middle)
Case 2: Two nodes
Input: head = [1,2]
Output: [2]
(Second middle for even length)
Case 3: Three nodes (odd)
Input: head = [1,2,3]
Output: [2]
(Node 2 is middle)
Case 4: Four nodes (even)
Input: head = [1,2,3,4]
Output: [3]
(Second middle)
Case 5: Large odd list
Input: head = [1,2,3,4,5,6,7,8,9]
Output: [5,6,7,8,9]
(Node 5 is middle)
All handled correctly! ✓
Related Patterns
- Reorder List (LC 143) - Uses middle finding
- Palindrome Linked List (LC 234) - Find middle, reverse
- Delete Middle Node (LC 2095) - Find then delete
Happy practicing! 🎯
Note: This is one of the most elegant uses of fast & slow pointers! The technique of "different speeds to find relative positions" is powerful and reusable! 🐢🐇