Fast and Slow Pointers: The Cycle Detection Interview Pattern
Some interview problems look like they need a hash set, extra memory, or a clever data structure, and then turn out to be solvable with two pointers moving at different speeds. That's the fast and slow pointers interview pattern, also called Floyd's tortoise and hare. It shows up in linked list problems, number sequences, and even array problems that secretly describe a linked structure.
This guide covers when to reach for it, the core templates, and how to explain why it works, which is often the part interviewers care about most.
When to recognize it
Look for these signals:
- "Detect whether a linked list has a cycle."
- "Return the node where the cycle begins."
- "Find the middle of a linked list in one pass."
- "Is this number happy?" or any sequence where each value determines the next.
- "Find the duplicate number" with constraints like no extra space and don't modify the array.
The common thread: you're following a chain of "next" values, and you want O(1) extra space.
Template 1: does a cycle exist?
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
Why it works, in one sentence: if there's a cycle, once both pointers are inside it, the fast pointer gains one step on the slow pointer each move, so it must eventually land on the same node; if there's no cycle, the fast pointer reaches the end.
Time is O(n), space is O(1). Compare that out loud with the hash-set approach (O(n) space) to show you chose deliberately.
Template 2: where does the cycle start?
def cycle_start(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
The explanation interviewers like: let the distance from the head to the cycle start be a, and the distance from the cycle start to the meeting point be b. When they meet, the fast pointer has traveled twice as far as the slow one. Working through the algebra shows that a equals the distance from the meeting point forward to the cycle start, modulo the cycle length. So if you reset one pointer to the head and move both one step at a time, they meet exactly at the start.
You don't need a perfect proof. A clear sketch with a and b on the whiteboard is usually enough.
Template 3: the middle of a linked list
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
For even-length lists this returns the second of the two middle nodes. If the problem needs the first middle (for example, to split a list for merge sort), start fast at head.next. Say which one you're returning; it's a classic off-by-one trap.
Common follow-ups that use this template:
- Palindrome linked list: find the middle, reverse the second half, compare.
- Reorder list: find the middle, reverse the second half, merge alternately.
- Sort a linked list: split at the middle for merge sort.
Template 4: sequences that aren't lists
"Happy number" asks whether repeatedly summing the squares of digits reaches 1. The sequence either hits 1 or loops forever. Treat next(n) as the "next pointer" and run the cycle check:
def is_happy(n):
def nxt(x):
return sum(int(d) ** 2 for d in str(x))
slow, fast = n, nxt(n)
while fast != 1 and slow != fast:
slow = nxt(slow)
fast = nxt(nxt(fast))
return fast == 1
Template 5: find the duplicate number
Given an array of n + 1 integers where each value is in 1..n, there must be a duplicate. If you treat each value as a pointer to an index (i -> nums[i]), the duplicate value is where a cycle begins. Apply Template 2 using nums[x] as x.next. It's O(n) time, O(1) space, and doesn't modify the array, which is exactly what the constraints usually demand.
Explaining the "values as pointers" reframing out loud is the key moment in this problem.
Common bugs
- Null checks in the wrong order. Always check
fast and fast.nextbefore moving two steps. - Comparing values instead of nodes. Use identity (
is) for nodes; values may repeat. - Starting positions. Changing where
faststarts changes which middle you get and can break the cycle-start math. - Forgetting the no-cycle case in Template 2.
How to talk through it
- Name the pattern: "This is a chain of next pointers, so I'll use fast and slow pointers for O(1) space."
- Mention the alternative: "A hash set works too but costs O(n) memory."
- Write the template.
- Explain why they meet in one sentence.
- Walk through a five-node example with a small cycle.
Rehearse the explanation
The code for this pattern is short; the explanation is where candidates get stuck under pressure. If you want a structured way to practice explaining patterns like this out loud before your interview, Luna Interview is built for rehearsal and calm prep—not for use during a live interview.
Checklist
- [ ] Recognizes "chain of next values" problems
- [ ] Writes the cycle check with correct null guards
- [ ] Explains why the pointers meet
- [ ] Can sketch the cycle-start argument with distances a and b
- [ ] Knows which middle node the template returns
- [ ] Can reframe the duplicate-number problem as a linked list
Rehearse with an AI interview copilot, then browse commonly reported interview questions.