Fast and Slow Pointers: The Cycle Detection Interview Pattern

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:

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:

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

How to talk through it

  1. Name the pattern: "This is a chain of next pointers, so I'll use fast and slow pointers for O(1) space."
  2. Mention the alternative: "A hash set works too but costs O(n) memory."
  3. Write the template.
  4. Explain why they meet in one sentence.
  5. 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