Middle of the Linked List
Find the middle node in a single pass using fast and slow pointers
Problem Statement
Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second one.
Input: 1 → 2 → 3 → 4 → 5
Output: node 3 (and everything after it: 3 → 4 → 5)
Input: 1 → 2 → 3 → 4 → 5 → 6
Output: node 4 (the second of the two middles)Intuition
With an array you would compute n / 2 and index straight to it. A linked list has no indexing — the only way to reach node k is to follow k pointers from the head.
The obvious fix is two passes: count the nodes, then walk halfway. That works and is O(n). But there is a one-pass method that generalises to a whole family of harder problems.
The key insight
Run two pointers from the head at different speeds:
slowadvances one node per stepfastadvances two nodes per step
When fast reaches the end, it has covered the whole list while slow has covered exactly half of it. So slow is standing on the middle. No counting, no second pass.
The arithmetic is simple: after k steps, slow is at index k and fast is at index 2k. fast finishes when 2k ≈ n, which is precisely when k ≈ n / 2.
Real-world analogy
Two runners on the same track, one at double the pace. The moment the faster runner crosses the finish line, the slower one is exactly at the halfway marker — without anyone measuring the track.
Watch it run
Approach
Loop while fast and fast.next both exist
Both checks are needed. fast might be null (even-length list), or fast.next might be null (odd-length list). Reading fast.next.next without them crashes.
Order the null checks correctly
while fast and fast.next — never while fast.next and fast. Both languages short-circuit left to right, so checking fast first guarantees you never dereference null.
Solution
from typing import Optional
class ListNode:
def __init__(self, val: int = 0, next: Optional["ListNode"] = None):
self.val = val
self.next = next
def middle_node(head: Optional[ListNode]) -> Optional[ListNode]:
"""Return the middle node; on a tie, the second middle."""
slow = fast = head
while fast and fast.next:
slow = slow.next # one step
fast = fast.next.next # two steps
return slowGetting the FIRST middle instead
Some problems want the first of the two middles. The fix is to start fast one node ahead — fast = head.next — or to loop while fast.next and fast.next.next. Knowing which variant you need, and that a one-line change switches between them, is the useful takeaway.
Complexity Analysis
Time Complexity
O(n)
Space Complexity
O(1)
- Time —
fasttraverses the list once;slowcovers half. Roughly1.5npointer hops, which isO(n). - Space — two references, regardless of list length. The count-then-walk alternative is also
O(n)time andO(1)space, but makes two passes — which matters when the data is streamed and can only be read once.
Edge Cases
Related Problems
- Linked List Cycle II — the same two pointers, used to detect and locate a loop
- Intersection of Two Linked Lists — two pointers over two different lists
- Reverse Linked List — the other essential linked-list building block