Fast & Slow — Middle of the Linked List
↗ LeetCode: Middle of the Linked List · Easy · pattern chapter →
Given the head of a singly linked list, return the middle node. If there are two middles, return the second.
Example 1 — 1 → 2 → 3 → 4 → 5 → node with value 3Example 2 — 1 → 2 → 3 → 4 → 5 → 6 → node with value 4 (second middle) Example 3 — 1 → 1
Constraints — 1 ≤ n ≤ 100. Brute two-pass (count then walk) is O(n) time but two full traversals — hot service pays 2x cache misses. Fast/slow single pass is O(n) time, ~10⁶ pointer chases with one traversal.
Interview timer00:00
Approach 1 — Two passes: count then jump
Intuition. Walk once to get length n; walk again n/2 steps.
ListNode middleNodeCount(ListNode head) {
int n = 0;
for (ListNode c = head; c != null; c = c.next) n++;
ListNode m = head;
for (int i = 0; i < n / 2; i++) m = m.next;
return m;
}Complexity — Time O(n); Space O(1).
Approach 2 — Fast & slow (canonical)
Insight from two-pass. fast at 2× speed reaches the end when slow is at the middle — exactly. Odd length: fast ends at last node, slow at true middle. Even length: fast at null, slow at second middle.
ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}Complexity — Time O(n); Space O(1).
Trap. If you use while (fast.next != null && fast.next.next != null) you get the first middle instead of the second. LC spec asks for second — the loop condition matters.
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Two passes | O(n) | O(1) | acceptable |
| Fast/slow | O(n) | O(1) | canonical — one pass |
When to use which
- Ship this → fast/slow pointers.
- "Return first middle" → switch loop condition to check
fast.next. - "Return both middles for even n" →
slowis second;slow.prev(if doubly-linked) is first. - Splitting into halves → fast/slow gives O(1) space split; use for Sort List.
Related problems
- Linked List Cycle — same technique for detection
- Linked List Cycle II — find entry
- Palindrome Linked List — split at middle, reverse half
- Sort List — merge sort using middle split