Fast & Slow Pointers
One pointer moving twice as fast as another detects cycles, finds the middle, and locates the nth-from-end in one pass.
On this page
Some linked-list questions look like they need a second pass or extra memory - "find the middle," "does it have a cycle," "find the node k from the end." The fast and slow pointer technique (also called Floyd's tortoise and hare) answers all of them in a single pass with O(1) space, by running two pointers at different speeds.
Two speeds, one pass
Run one pointer (slow) one step at a time and another (fast) two steps at a time. Their relative
speed is what does the work. When fast reaches the end, slow is exactly halfway - so you've found
the middle without knowing the length:
// find the middle node in one pass — O(n) time, O(1) space
ListNode middle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next; // +1
fast = fast.next.next; // +2
}
return slow; // fast covered 2x, so slow is at the midpoint
}Cycle detection: the tortoise and hare
The most famous use: does a linked list have a cycle? If it does, the fast pointer will eventually
lap the slow one and they'll meet inside the loop - like a faster runner catching a slower one on a
circular track. If fast reaches null, there's no cycle.
// detect a cycle — O(n) time, O(1) space (no hash set needed)
boolean hasCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) return true; // they met → cycle
}
return false; // fast hit the end → no cycle
}Why must they meet if there's a cycle? Once both pointers are inside the loop, fast gains one step
on slow every iteration, so the gap between them shrinks by one each time - it can never jump over,
so it must eventually reach zero. This gives O(1) space, versus the obvious O(n)-space solution of
storing visited nodes in a hash set.
The nth from the end
The same idea with a fixed gap finds the k-th node from the end in one pass: advance fast k
steps first, then move both together until fast hits the end - now slow is k from the end.
Guard the fast pointer
fast moves two steps, so both fast and fast.next can be null. The loop condition must check
fast != null && fast.next != null (in that order, so short-circuiting prevents a
NullPointerException). Getting this guard wrong is the most common bug in fast/slow code.
Two runners start together; one runs twice as fast. On a straight track, the fast runner simply finishes first and leaves - no meeting. On a circular track, the fast runner keeps lapping and will inevitably come up behind the slow one and draw level. That's cycle detection: put two pointers on the list at different speeds - if the 'track' loops, they meet; if it ends, the fast one runs off the edge. And at the moment the fast runner has done a full lap, the slow one is exactly halfway - which is why the same trick finds the middle.
Determine whether a singly linked list reads the same forwards and backwards, using O(1) extra space. Combine two techniques you now know to do it in one pass plus a reversal.
Why do fast and slow pointers meet if (and only if) a linked list has a cycle?
Key takeaways
- Fast and slow pointers move at different speeds (typically 2x and 1x) to solve linked-list problems in one pass, O(1) space.
- When fast reaches the end, slow is at the middle - finding the midpoint without knowing the length.
- Floyd's cycle detection: if a cycle exists, fast laps slow and they meet; otherwise fast reaches null.
- A fixed k-step head start finds the k-th node from the end in one pass.
- Guard the loop with fast != null && fast.next != null (order matters) to avoid a NullPointerException.