Pattern visualizer
Middle of Linked List
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. Animated on: list = [1,2,3,4,5] — find the middle node in a single pass, without knowing the length ahead of time..
Fast pointer moves 2x speed — it hits the end exactly when slow hits the middle
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.
1FUNCTION middleNode(head):2 slow = head; fast = head3 WHILE fast is not empty and the node after fast is not empty:4 move slow one node forward5 move fast two nodes forward6 RETURN slow
← / → step · space play · Home restart