Detect cycles and find midpoints in linked structures with two pointers moving at different speeds.
What the fast and slow pointers pattern is
Run two pointers through the same sequence at different speeds - classically, slow moves one step per turn while fast moves two. Their relative motion answers questions that a single pass cannot: if the structure loops, the fast pointer must eventually lap the slow one inside the loop; if it doesn't loop, fast reaches the end when slow is exactly halfway. One traversal, O(1) extra memory, and no modification of the structure.
This is Floyd's tortoise-and-hare technique. The alternative for cycle detection - a visited set - costs O(n) memory; fast and slow pointers get the same answer in constant space, which is exactly the trade interviewers probe for.
How to recognize it
Reach for it when the input is a linked structure (linked list, or an array interpreted as pointers via indices) and the question involves cycles, midpoints, or an unknown length: 'does this list have a cycle', 'where does the cycle start', 'find the middle node', 'is this number happy'. Any sequence generated by repeatedly applying a function - like x -> nums[x] - is secretly a linked list, so cycle questions about such sequences are this pattern in disguise.
The tell is O(1) space. If you're allowed a hash set, most of these are trivial; the pattern exists for when you're not.
Why the hare must catch the tortoise
Once both pointers are inside a cycle, look at the gap between them. Each turn, fast closes the gap by exactly one (it gains two steps, slow escapes one). A gap that shrinks by one each turn must hit zero - it cannot jump over - so they meet. This is the proof to say out loud in an interview: not 'they will probably collide' but 'the gap decreases by exactly one per step, so collision is inevitable within one lap'.
The follow-up that separates candidates: after meeting, reset one pointer to the head and advance both one step at a time - they meet again exactly at the cycle's entry. That works because the distance from head to entry equals the distance from the meeting point forward to the entry (mod cycle length), a consequence of fast having traveled exactly twice as far as slow.
pseudocode
slow = head, fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: # cycle confirmed
slow = head # phase 2: find the entry
while slow != fast:
slow = slow.next
fast = fast.next
return slow # cycle entry
return null # fast fell off: no cycle
Complexity
O(n) time: slow never takes more than n steps before the answer is known, and fast takes at most 2n. O(1) space always - that is the entire point. For midpoint problems, when fast hits the end, slow sits at the middle (with a one-node choice for even lengths that you should state explicitly).
Common pitfalls
Advancing fast without checking both fast and fast.next - the null-pointer crash every interviewer has seen a hundred times. The loop guard is `while fast and fast.next`.
Starting the meeting check before moving: if both start at head and you test equality first, you 'detect' a cycle immediately. Move, then compare.
Even-length midpoints: fast-slow lands slow on the second middle node by default. For 'split the list in half' problems you usually want the first - start fast one step ahead or track the previous node. Decide before coding, not after the bug.
Forgetting the phase-2 reset rule for cycle entry and trying to derive it live - memorize the reset-to-head trick and be ready to justify it.
Worked examples
1. Linked list cycle detectioneasy
Given the head of a linked list, determine whether the list contains a cycle. Use O(1) memory.
A visited set solves this in O(n) memory; the constraint pushes us to two speeds instead.
Advance slow by one and fast by two per turn, guarding on `fast and fast.next`.
If fast reaches null, the list terminates - no cycle. If the pointers ever coincide after moving, there is a cycle: the gap inside the loop shrinks by one each turn, so meeting is guaranteed.
Return true on meeting, false on falling off the end. O(n) time, O(1) space.
pseudocode
slow = head, fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast: return true
return false
Remember: Inside a loop, a 2x pointer closes the gap by exactly one per step - collision is a certainty, not a coincidence.
2. Middle of the linked listeasy
Return the middle node of a singly linked list in one pass. If there are two middle nodes, return the second.
Two passes (count, then walk half) is easy but the one-pass version shows the pattern: when fast has gone twice as far, slow is at the midpoint by definition.
Advance slow one, fast two, until fast runs out of list.
For odd lengths fast lands on the tail and slow on the exact middle; for even lengths fast hits null and slow lands on the second middle - which is what this problem wants. State that choice out loud.
Return slow. This same positioning trick powers palindrome checks and list-reordering problems.
pseudocode
slow = head, fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Remember: 'Half as fast' means 'halfway there' the moment the fast pointer finishes - no counting pass needed.
3. Find the duplicate numbermedium
An array of n+1 integers has values in [1, n], so at least one value repeats. Find the duplicate without modifying the array and in O(1) space.
Treat each index as a node whose next pointer is nums[index]. Because values stay in [1, n], the walk x -> nums[x] never leaves the array - it is a linked structure.
A duplicated value means two indices point at the same node: the structure must contain a cycle, and the duplicate is exactly the cycle's entry.
Run phase 1 (slow x1, fast x2) from index 0 until they meet inside the cycle.
Run phase 2: reset one pointer to 0, advance both by one; the meeting point is the cycle entry, i.e. the duplicated value. No mutation, O(1) space.
pseudocode
slow = nums[0], fast = nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Remember: An array whose values are valid indices is a hidden linked list - duplicates become cycle entries, and Floyd finds them without touching memory.
Check yourself
Try to answer before revealing - retrieving from memory is what makes it stick.
1Why is the fast pointer guaranteed to meet the slow pointer if a cycle exists?
Because both pointers eventually visit every node
✓ Because the gap between them shrinks by exactly one each step once both are in the cycle, so it must reach zero
Because the fast pointer wraps around to the head
It isn't guaranteed - it depends on the cycle length being even
Fast gains one net step on slow per turn inside the cycle. A gap that decreases by exactly one cannot skip zero, so a meeting is inevitable within one lap regardless of cycle length.
2After the pointers meet inside a cycle, how do you locate the cycle's entry node?
It is always the meeting node
✓ Reset one pointer to the head; advance both one step at a time; where they meet is the entry
Count the cycle length and subtract it from the list length
Reverse the list and walk back
Because fast traveled exactly twice slow's distance, head-to-entry equals meeting-point-to-entry (mod cycle length). Walking both at equal speed makes them converge precisely at the entry.
3What is the correct loop guard when advancing fast by two?
while fast
while slow and fast
✓ while fast and fast.next
while fast.next and fast.next.next
fast.next.next dereferences fast.next, so both fast and fast.next must be non-null before stepping. This guard also cleanly terminates acyclic lists of odd or even length.
4Why does 'Find the Duplicate Number' qualify as a fast-slow pointers problem when there is no linked list in sight?
It doesn't - it is a binary search problem only
✓ The array's values are valid indices, so x -> nums[x] forms a hidden linked structure whose cycle entry is the duplicate
Sorting the array creates a linked list
Fast and slow refer to two different arrays
With n+1 values in [1, n], following nums[x] never escapes the array, and pigeonhole forces two indices to share a target - a cycle whose entry is the repeated value. The structure is a function graph, which is a linked list with a loop.
Frequently asked questions
When should I use fast-slow pointers instead of a hash set?
When memory is constrained to O(1) or the interviewer asks for it. A hash set of visited nodes also detects cycles and is simpler - but it costs O(n) space, and the follow-up 'can you do it without extra memory?' is precisely where this pattern lives.
Does the speed have to be exactly 2x?
Any distinct speeds detect a cycle eventually, but 1x/2x is standard because it gives the clean guarantees: meeting within one lap, and the reset-to-head trick for finding the cycle entry depends on fast having traveled exactly twice as far.
How do fast-slow pointers find the middle for even-length lists?
With both starting at head, slow lands on the second of the two middles. If a problem needs the first middle (splitting a list in half, palindrome checks), start fast at head.next or remember slow's previous node - and say which convention you chose.