Middle of the Linked List
Find the middle node of a linked list in one pass with slow and fast pointers: when fast reaches the end, slow is halfway.
Problem Understanding
Middle of the Linked List: given the head of a singly linked list, return its middle node. If there are two middle nodes, return the second one.
Example: [1, 2, 3, 4, 5] returns the node 3; [1, 2, 3, 4, 5, 6] returns the node 4.
The Intuition: One Pointer at Double Speed
A linked list has no index, so you cannot jump to n / 2. Instead send two pointers down it at different speeds:
- slow moves one node per round.
- fast moves two nodes per round.
- When fast cannot take two more steps, it has covered the whole list, so slow has covered exactly half.
This fast-and-slow technique is a core linked list pattern: the same pointers detect loops in Linked List Cycle and find the split point in Palindrome Linked List and Reorder List.
Interactive Walkthrough
BOTH AT HEAD
slow fast
0
→
1
→
2
→
3
→
4
→
NULL
slow
1
fast
1
Middle
—
slow and fast both start at the head
Next
slow moves 1 to 2; fast moves 2 to 3
head
Legend & Complexity
slow, one node per round
fast, two nodes per round
The middle node
Time
O(n)
Space
O(1)
slow is filled and fast is outlined; when fast runs off the end, its marker moves to NULL. Try Example 2 to see an even-length list stop on the second middle.
Dry Run Table
Input: head = [1, 2, 3, 4, 5, 6]
| Round | slow | fast |
|---|---|---|
| start | 1 | 1 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| 3 | 4 | NULL |
fast is NULL, so the loop stops. Answer: the node 4.
The Solution Template
Two pointers, one loop. The loop condition checks fast before fast.next, so fast never steps past NULL.
Middle of the Linked List Code
1var middleNode = function(head) {2 let slow = head, fast = head;3 while (fast && fast.next) {4 slow = slow.next;5 fast = fast.next.next;6 }7 return slow;8};
Edge Cases & Common Mistakes
- One node: fast.next is NULL, so the loop never runs and the head is returned.
- Two nodes: one round moves slow to the second node, the second middle.
- Checking only
fast.next: crashes when fast itself is NULL on even lengths; testfastfirst. - Needing the first middle: loop while
fast.next && fast.next.nextinstead. - Two passes: counting first is fine but not necessary; one pass with two pointers is the expected answer.
Summary
Start slow and fast at the head. While fast and fast.next exist, move slow one node and fast two. When the loop stops, slow is the middle (the second middle for even lengths). O(n) time and O(1) space.
More practice: DSA interview questions with answers · patterns cheat sheet