On this page
Description
Two pointers on a linked list find positions you'd otherwise need the length for. A slow pointer moving one step and a fast pointer moving two find the middle in one loop. Two pointers kept a fixed n nodes apart find the n-th node from the end. They're the building blocks of Middle of the Linked List, Remove Nth Node From End, palindrome checks, and splitting a list for merge sort.
We'll go from simple to more technical:
- The pattern: fast and slow pointers find the middle.
- A second flavor: a fixed gap finds a position from the end.
- Where two-speed and fixed-gap walks show up elsewhere.
- The even-length and remove-the-head edge cases.
The approach: fast/slow to find the middle
The obvious way to find the middle is to count the nodes, then walk half that far. Two pointers do it in one loop with no counter. fast moves two steps for each step of slow. So when fast reaches the end, slow has gone exactly half as far: it's at the middle.
Finding the middle of 3 -> 8 -> 1 -> 6 -> 2:
| Step | slow | fast |
|---|---|---|
| Start | 3 | 3 |
| 1 | 8 | 1 |
| 2 | 1 | 2: fast.next is null, so stop |
The middle is 1. To be precise about the gain: the two pointers don't do less walking than counting first. What they remove is the separate counting pass and the length variable.
Java
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
// slow is now at the middle - fast has traveled twice as far,
// so when fast reaches the end, slow is exactly halfway.
Python
slow = fast = head
while fast is not None and fast.next is not None:
slow = slow.next
fast = fast.next.next
# slow is now at the middle - fast has traveled twice as far,
# so when fast reaches the end, slow is exactly halfway.
On an even-length list there are two middles. For 3 -> 8 -> 1 -> 6, this loop stops with slow on 1, the second one.
A second flavor: fixed gap to find a position from the end
To remove the n-th node from the end, move fast n steps ahead first. Then move both pointers together until fast reaches the last node. slow is then n nodes behind it: just before the node to remove. Both start at a dummy node placed before the head, so removing the head itself needs no special case.
Removing the 2nd node from the end of 3 -> 8 -> 1 -> 6 -> 2: fast first moves 2 steps, to 8. Then both move until fast is on 2, the last node. slow ends on 1, so slow.next = slow.next.next unlinks 6, leaving 3 -> 8 -> 1 -> 2.
Java
ListNode fast = dummy, slow = dummy; // dummy.next = head, handles removing the head cleanly
for (int i = 0; i < n; i++) fast = fast.next; // open up a gap of n nodes
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// slow is now just BEFORE the nth node from the end - its predecessor,
// so slow.next = slow.next.next removes it
Python
fast = slow = dummy # dummy.next = head, handles removing the head cleanly
for _ in range(n):
fast = fast.next # open up a gap of n nodes
while fast.next is not None:
fast = fast.next
slow = slow.next
# slow is now just BEFORE the nth node from the end - its predecessor,
# so slow.next = slow.next.next removes it
Both patterns answer a question about position relative to the length, in one loop, without ever knowing the length.
Where you'll see it
The two-speed idea is also how cycle detection works (see Cyclic Sequence Detection). The fixed gap is the same idea as keeping the last N events of a stream you can't index backward.
Which tool for which job?
| You need | Use |
|---|---|
| The middle (second of two on even length) | while fast and fast.next |
| The first middle (to split a list in half) | while fast.next and fast.next.next |
| The n-th node from the end | two pointers n apart, from a dummy |
| Remove the n-th from the end | the gap technique, stopping one node before it |
| The n-th from the end of a read-once stream | a buffer of the last n items |
| Detect a cycle | fast/slow (see Cyclic Sequence Detection) |
Common mistakes
| Mistake | What happens | Do this instead |
|---|---|---|
| The wrong middle on even lengths | off by one node | pick the loop condition for the middle you need |
| Splitting after the second middle | a 2-node list splits into 2 and 0 - merge sort never ends | split after the first middle |
| No dummy when removing from the end | removing the head crashes | start both pointers at a dummy |
| Not checking n against the length | null dereference | validate n, or return the list unchanged |
| Expecting fewer steps than counting | same ~1.5L hops | the win is one loop, not less work |
Check yourself
Try to answer before opening each one - recalling beats re-reading.
1. On an even-length list, why does while (fast != null && fast.next != null) stop on the second middle?
Show answer
On an even-length list, fast steps past the last node to null just as slow reaches the second middle. Adding fast.next.next != null to the condition stops one round earlier, on the first middle. Pick the condition for the middle the problem wants, and check it on a four-node list.
2. Why does "remove the n-th node from the end" start both pointers at a dummy node?
Show answer
If the node to remove is the head, there's no node before it to rewire. With a dummy in front, the head has a predecessor like every other node, so the same slow.next = slow.next.next removes it too.
3. How do fast and slow find the middle without knowing the length?
Show answer
fast always covers twice the distance of slow. When fast reaches the end, after L nodes, slow has covered L/2. The relationship between the two pointers stands in for "half the length", so the number itself is never needed.
Key takeaways
- Two pointers at different speeds, or a fixed gap apart, answer "where relative to the length" in one loop.
- An even-length list has two middles. The loop condition decides which one you get.
- A dummy node before the head lets you remove the head like any other node.
- Two pointers don't save steps over counting first. They save the counting pass.