Middle of the Linked List

Fast pointer moves 2x speed — it hits the end exactly when slow hits the middle

time O(n)space O(1)

Counting the list length first would take a full pass, then finding the middle would take a second pass. Instead, run two pointers at different speeds in ONE pass: if fast always covers exactly twice the distance slow does, then the moment fast reaches the end, slow — having covered exactly half that distance — is sitting right at the middle.

Details

Animated on: list = [1,2,3,4,5] — find the middle node in a single pass, without knowing the length ahead of time.

Problem:Middle of the Linked ListEasy

Pattern:Fast and Slow Pointers

Fast pointer moves 2x speed — it hits the end exactly when slow hits the middle

step 1 / 4

[0]

[1]

[2]

[3]

[4]

List = [1,2,3,4,5]. slow and fast both start at the head. fast moves 2 steps for every 1 slow moves — when fast runs out of list, slow is exactly at the middle.

slow=0· arr[0] = 1
fast=0· arr[0] = 1

Pseudocode

1FUNCTION middleNode(head):
2  slow = head; fast = head
3  WHILE fast is not empty and the node after fast is not empty:
4    move slow one node forward
5    move fast two nodes forward
6  RETURN slow

← / → step · space play · Home restart

Every step in words

Show all 4 steps

List = [1,2,3,4,5]. slow and fast both start at the head. fast moves 2 steps for every 1 slow moves — when fast runs out of list, slow is exactly at the middle.
slow -> index 1 (2), fast -> index 2 (3).
slow -> index 2 (3), fast -> index 4 (5).
fast can no longer take a full 2-step hop, so the loop stops. slow is at index 2 — the middle node, value 3.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Middle of the Linked List in the editor All Linked List problems Back to roadmap