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
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.nextbefore 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.