Fast and Slow Pointers: The Cycle-Detection Pattern for Coding Interviews

The fast and slow pointer technique (Floyd's tortoise and hare) solves a whole group of interview problems with O(1) extra space. One pointer moves one step at a time, the other moves two. If there's a loop, they must meet; if there isn't, the fast pointer hits the end.

1. Detect a cycle in a linked list

⎗
✓
1
2
3
4
5
6
7
def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            return True
    return False

Explain why it terminates: once both pointers are inside the cycle, the gap between them shrinks by one each step.

2. Find where the cycle starts

After they meet, reset one pointer to the head and move both one step at a time. They meet again at the cycle's entrance. Interviewers love asking why: the distance from head to the entrance equals the distance from the meeting point to the entrance (modulo the cycle length). Sketch it with a small diagram.

3. Middle of a linked list

When the fast pointer reaches the end, the slow pointer is at the middle. Clarify which middle they want for even lengths.

4. Happy number

Repeatedly replacing a number with the sum of the squares of its digits either reaches 1 or loops forever. Treat the sequence as an implicit linked list and run cycle detection instead of storing every value in a set.

5. Find the duplicate number (values 1..n in an array of n+1)

Treat nums[i] as a "next" pointer. A duplicate value means two indices point to the same node, which creates a cycle, so the cycle entrance is the duplicate. O(n) time, O(1) space, and the array is not modified.

6. Palindrome linked list

Find the middle with fast/slow pointers, reverse the second half, compare, and (politely) restore the list afterwards.

Talking points that earn credit

  • Mention the hash-set alternative first (O(n) space), then improve to O(1).
  • Guard fast and fast.next before every double step.
  • Test with an empty list, a single node, and a cycle that loops back to the head.

Practising these out loud is the fastest way to make them automatic. For mock coding interviews with follow-up questions, see linkjob.ai.

Disclosure: written by the Linkjob AI team.

Edit

Pub: 01 Nov 2026 19:15 UTC

Views: 6