Find the middle Element of a linked list
Find the Middle Element of a Linked List
Problem Statement
Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes (even length), return the second middle node.
Example
Input: 1 -> 2 -> 3 -> 4 -> 5 -> null
Output: Node with value 3
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Output: Node with value 4 (second middle)
Input: 1 -> null
Output: Node with value 1
Brute Force Approach (Two Pass)
Intuition
First, count the total number of nodes. Then traverse again to the middle position.
Algorithm
- First pass: Count the total number of nodes (n)
- Calculate middle position: mid = n/2
- Second pass: Traverse to the middle node
- Return the middle node
Implementation
Complexity Analysis
- Time Complexity: O(n) - Two passes through the list
- Space Complexity: O(1) - Only using a few variables
Optimal Approach (Slow and Fast Pointers)
Intuition
Use two pointers: slow moves one step at a time, fast moves two steps. When fast reaches the end, slow will be at the middle.
This works because fast travels twice as fast as slow:
- When fast reaches the end (n steps), slow is at n/2 (the middle)
Algorithm
- Initialize both slow and fast pointers at head
- While fast and fast.next are not null:
- Move slow one step forward
- Move fast two steps forward
- When fast can't move anymore, slow is at middle
- Return slow
Visualization
Odd length: 1 -> 2 -> 3 -> 4 -> 5 -> null
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: fast.next is null, stop
Middle = 3 ✓
Even length: 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
Step 0: slow=1, fast=1
Step 1: slow=2, fast=3
Step 2: slow=3, fast=5
Step 3: slow=4, fast=null (fast is null, stop)
Middle = 4 (second middle) ✓
Implementation
Complexity Analysis
- Time Complexity: O(n) - Single pass (fast traverses full list)
- Space Complexity: O(1) - Only using two pointers
Variant: Return First Middle for Even Length
If you need to return the first middle when there are two middle nodes:
Alternative: Using Array (Not Recommended)
Store all nodes in an array and return the middle element. This uses O(n) extra space and is not preferred.
Applications of Finding Middle
The middle-finding technique is used in many problems:
- Merge Sort: Split list into two halves
- Palindrome Check: Find middle, reverse second half, compare
- Reorder List: L0→Ln→L1→Ln-1...
- Split Circular List: Divide into two halves
Comparison of Approaches
| Approach | Time | Space | Passes | |----------|------|-------|--------| | Two Pass | O(n) | O(1) | 2 | | Slow-Fast | O(n) | O(1) | 1 | | Array | O(n) | O(n) | 1 |
Key Takeaways
- Slow-fast pointer technique is the most elegant solution
- This is a fundamental technique used in many linked list problems
- For second middle (even length): use
while (fast && fast.next) - For first middle (even length): use
while (fast.next && fast.next.next) - The technique works because fast travels twice the distance of slow
- This is a classic interview problem (LeetCode #876)
- Understanding this pattern is essential for cycle detection and merge sort