Middle of a Linked List

Middle of the Linked List is the cleanest introduction to the fast & slow pointer technique — one of the most reused tricks for linked lists. It finds the center in a single pass without ever counting the length.

The slow way first

The obvious idea: walk the whole list once just to count the nodes, work out that the middle is at index length // 2, then walk a second time to reach it. That works and it is O(n) time, but it makes two passes over the list.

The question to ask: can I find the middle without knowing the length up front? Yes — if I send one pointer twice as fast as another, the slow one is at the halfway mark exactly when the fast one runs out of list.

The idea: one pointer at double speed

Start two pointers, slow and fast, at the head. On each loop, move slow forward one node and fast forward two. Because fast covers ground twice as quickly, when fast reaches the end slow has only made it halfway — which is precisely the middle.

The key insight is the ratio: fast always sits at twice slow's distance from the head. The loop keeps going only while fast and fast.next both exist — that condition is what makes slow land on the second middle when the list length is even.

Walk through it

Step through the animation. Both markers begin on node 1. Loop one: slow slides to 2, fast to 3. Loop two: slow slides to 3, fast to 5 — the last node. Now fast.next is None, so the loop stops, and slow is parked on 3, the middle.

Pseudocode

slow = fast = head
while fast exists and fast.next exists:
    slow = slow.next            # advance one node
    fast = fast.next.next       # advance two nodes
return slow                     # slow is now the middle

The Python solution

def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

• slow = fast = head starts both pointers on the first node.
• while fast and fast.next keeps looping only while fast has two more nodes to jump over; the moment either check fails we have reached the end.
• slow = slow.next advances the slow pointer one node.
• fast = fast.next.next advances the fast pointer two nodes — double the speed.
• When the loop exits, slow is at the middle, so we return slow.

Complexity

Both approaches are O(n) time, but the fast & slow version uses only two pointers — O(1) extra space — and finishes in a single pass. That tidy constant-space, one-pass quality is exactly why interviewers love it.

When this pattern shows up

Practice