Pattern6 min read
Fast & Slow Pointers (Floyd's)
One pointer moves twice as fast as the other — used to detect cycles and find midpoints in linked lists.
linked-listtwo-pointers
Intro
Two pointers, one moving by 1 step and another by 2 steps, will eventually meet inside any cycle. They will never meet on a list that has no cycle, because the fast pointer reaches null first.
Key insight
When fast and slow meet, the distance from list head to the cycle entry equals the distance from the meeting point to the cycle entry — restart one pointer at the head and they meet at the cycle start.
Approach
- 1Initialise slow = head, fast = head.
- 2Move slow by 1, fast by 2 each loop.
- 3If they meet, you have a cycle. If fast hits null, no cycle.
- 4To find the cycle's start: reset slow to head, advance both by 1 until they meet again.
Complexity
Time
O(n)
Space
O(1)
Code
Snippetjava
ListNode detectCycle(ListNode head) {
ListNode slow = head, fast = head;
while (fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
if (slow == fast) {
ListNode p = head;
while (p != slow) { p = p.next; slow = slow.next; }
return p;
}
}
return null;
}Pitfalls
- Advancing `fast` without checking `fast.next != null` — NullPointerException on odd-length lists.
- Trying to use this pattern on a doubly-linked list — usually overkill; simpler patterns work.
Variants & follow-ups
- Happy Number (LC 202)
- Find Middle of Linked List (LC 876)
- Linked List Cycle II (LC 142)