Find Middle of Linked List —
Slow and fast. One pass. No length.
Finding the middle node without knowing the length uses slow and fast pointers. Fast moves twice as fast as slow — when fast reaches the end, slow is exactly at the middle. Watch both pointers advance on LearnBug and the geometric reasoning becomes immediately obvious.
Why not just count the length?
You could traverse the list to find n, then traverse again to position n/2. That's two passes. The slow/fast pointer technique does it in one pass — and works even if you can't traverse the list twice (e.g. a stream). It's also the building block for palindrome check and merge sort on linked lists.
The geometric insight
If fast moves twice as fast as slow, when fast has covered the whole list (n steps), slow has covered exactly half (n/2 steps). They start together and fast laps the list while slow walks half of it — when fast is done, slow marks the midpoint. On LearnBug both pointers are visible at every step.
Odd-length: 1→2→3→4→5 and Even-length: 1→2→3→4
List: 1→2→3→4→5 (length 5)
Step 1: slow=2, fast=3. Step 2: slow=3, fast=5. fast.next=None → stop. slow is at node 3 — the true middle ✓
Middle = node 3 ✓
List: 1→2→3→4 (length 4)
Step 1: slow=2, fast=3. Step 2: slow=3, fast=None (fast.next.next=None) → stop. Slow is at node 3 — second middle (upper mid). For first middle, use while fast.next and fast.next.next.
Middle = node 3 (second middle for even-length)
Both middle variants
def middle_node(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # for even length: returns second middledef middle_node_lower(head):
slow = fast = head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
return slow # for even length: returns first middleTime & Space Complexity
Frequently asked questions
For an even-length list, which middle does each variant return?
With condition while fast and fast.next: returns the second (upper) middle — for list 1→2→3→4, returns node 3. With condition while fast.next and fast.next.next: returns the first (lower) middle — returns node 2. For merge sort on linked lists, the first middle is used so the split produces a left list of n/2 and right of n/2 (or n/2+1 for odd).
How is this used in merge sort on a linked list?
Find the middle, split the list there (set slow.next = None), recursively sort each half, then merge. Finding the middle in O(1) space and O(n) time is essential — it's what makes in-place merge sort on a linked list possible. LeetCode 148 — Sort List.
How is this used in palindrome check?
Find the middle, reverse the second half, then compare the first half and reversed second half node by node. If all values match — palindrome. This is O(n) time and O(1) space. LeetCode 234 — Palindrome Linked List combines find middle + reverse linked list.
What is the LeetCode problem for this?
LeetCode 876 — Middle of the Linked List. A straightforward problem that is itself rarely asked in isolation — it's more commonly a sub-problem inside LC 148 (Sort List) and LC 234 (Palindrome Linked List). Knowing how to find the middle efficiently is a prerequisite for those harder problems.
Can I find the middle by converting to an array?
Yes — copy all values to an array, return the element at index len//2. This is O(n) time and O(n) space. The two-pointer approach achieves O(n) time with O(1) space. In an interview, always mention the two-pointer approach as the optimal solution even if you start with the array approach.
Watch slow stop at exactly the middle as fast finishes
Paste your linked list into LearnBug and see both pointers advance until fast reaches the end.