Fast & slow pointers
In one line
Move one pointer one step and another two steps at a time: if there is a cycle the fast one laps the slow one, and if there is none the slow one ends at the middle when the fast one hits the end.
What it is
Fast and slow pointers (Floyd's tortoise and hare) walk the same sequence at different speeds, usually 1 and 2 steps per move. The sequence can be a linked list, or any process where each value determines the next one, such as an array where nums[i] says where to go next.
Two facts make it useful. If the sequence ends, fast reaches the end after n / 2 moves, at which point slow is at the middle. If the sequence loops, fast enters the loop and gains one step on slow every move, so they must meet inside the loop. Both use O(1) memory, unlike storing visited nodes in a hash set.
Why interviewers ask
Cycle detection, finding the middle of a linked list and finding the duplicate number are classic questions that specifically ask for O(1) space. Interviewers check that you handle null pointers safely, and strong candidates can explain why the pointers meet and why resetting one pointer to the head finds the cycle's start.
How it works
- 1Start slow and fast at the head. Loop while fast and fast.next exist: slow = slow.next, fast = fast.next.next.
- 2No cycle: fast runs off the end. If the loop stops there, slow is at the middle (the second middle for even lengths).
- 3Cycle: once both are in the loop, the gap between them shrinks by 1 each move, so they meet within one lap.
- 4Find the cycle start: let a be the distance from head to the cycle start, b the distance from the start to the meeting point, c the cycle length. Slow walked a + b and fast walked twice that, and the extra a + b is a whole number of laps, so a + b = k * c. That means a = k * c - b.
- 5So reset slow to the head and move both one step at a time: after a steps slow reaches the start, and fast, which began b steps into the loop, has also walked to the start. They meet there.
- 6Implicit lists: the same works on sequences like 'replace n by the sum of the squares of its digits' (happy number) or i -> nums[i] (find the duplicate).
Worked example · List 1 -> 2 -> 3 -> 4 -> 5, where 5 points back to 3
- Start: slow = 1, fast = 1.
- Move 1: slow = 2, fast = 3.
- Move 2: slow = 3, fast = 5.
- Move 3: slow = 4, fast goes 5 -> 3 -> 4, so fast = 4. They meet at node 4: there is a cycle.
- Phase 2: slow = 1 (head), fast stays at 4. Step: slow = 2, fast = 5. Step: slow = 3, fast = 3. They meet at node 3, the cycle start.
- Check with the formula: a = 2 (1 -> 2 -> 3), b = 1 (3 -> 4), c = 3. a + b = 3 = 1 * c, as predicted.
Picture it
Two runners on a track, one twice as fast. On a straight road the fast one simply reaches the finish first, and the slow one is halfway. On a circular track the fast one eventually comes up behind the slow one and passes them, which proves the track is a loop.
Reference code
class ListNode:
def __init__(self, val, next=None):
self.val = val
self.next = next
def detect_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 1 step
fast = fast.next.next # 2 steps
if slow is fast: # met inside the cycle
slow = head
while slow is not fast: # both move 1 step now
slow = slow.next
fast = fast.next
return slow # first node of the cycle
return None # fast hit the end: no cycle
def middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # second middle for even lengths
detect_cycle runs Floyd's algorithm: the while condition checks fast and fast.next before taking two steps, so it never dereferences None. After a meeting it resets slow to head; because a = k * c - b, both pointers then arrive at the cycle start together. middle() returns the second middle node for even-length lists. Both are O(n) time and O(1) space.
Key patterns
Cycle detection
When: Does a linked list or iterated function loop?
How: slow 1 step, fast 2 steps; meeting means a cycle, fast reaching null means none.
Cycle start
When: Where does the loop begin? (Linked List Cycle II, find the duplicate number)
How: After meeting, reset one pointer to the head and move both 1 step; they meet at the start.
Middle of a list
When: Split a list for merge sort, check a palindrome list
How: Stop when fast cannot move two steps; slow is at the middle.
Implicit sequence
When: Happy number, find duplicate in [1..n] array without modifying it
How: Use f(x) as next: sum of squared digits, or nums[x]; apply Floyd to the sequence of values.
Fixed gap (k apart)
When: Remove the k-th node from the end
How: Advance fast k steps first, then move both 1 step; when fast reaches the end, slow is just before the target.
Real-world use
Pollard's rho factorisation
Pollard's rho algorithm for factoring integers iterates x -> x^2 + c mod n and uses Floyd's (or Brent's) cycle detection to find a repeat modulo a hidden factor, needing only O(1) memory. It is implemented in tools such as SymPy's factorint.
Cryptanalysis and hash collisions
Rho-style collision search on hash functions and the rho method for discrete logarithms iterate a function and detect when it cycles, finding collisions without storing every value seen.
Random number generator testing
Floyd and Brent cycle detection are used to measure the period of a pseudo-random generator, that is how many outputs it produces before repeating, using constant memory.
Linked list algorithms in libraries
Merge sort on linked lists splits the list at its middle, found with slow and fast pointers in one pass without knowing the length in advance.
In a project
A workflow engine lets users chain steps where each step names its next step. A misconfigured chain can loop forever, and the validator must detect loops in chains of up to millions of steps on a memory-limited worker.
- Treat each workflow as an implicit linked list: next(step) = step.next_step_id.
- Run fast and slow pointers from the first step; if fast reaches a step with no next, the chain is valid.
- If they meet, reset one pointer to the first step and advance both one step at a time to find the first step of the loop.
- Report the loop's start step and its length (walk once around from the meeting point counting steps) in the validation error.
Impact: Infinite workflows are rejected at save time instead of hanging workers in production, the check uses constant memory however long the chain is, and users see exactly which step creates the loop.
Trade-offs
Use it when
- You need cycle detection or the middle of a sequence in O(1) space
- The structure is a singly linked list or an implicit next-function
- You cannot modify the input (for example find the duplicate without marking)
Avoid it when
- Memory is not a concern and you also need every visited node: a hash set is simpler
- You have random access to an array: just compute the middle index
- The next-function is expensive; fast evaluates it about twice as often (Brent's algorithm calls it less)
Cost: O(n) time, where n is the number of nodes (for a cycle, slow is caught within one lap after entering it). O(1) extra space.
Common mistakes
- Checking only fast.next and not fast first (or the reverse), which crashes on even or odd lengths.
- Comparing values instead of node identity; two different nodes can hold the same value.
- Starting fast at head.next in one place and head in another, which changes which middle you get and can break the cycle-start step.
- Claiming the meeting point is the cycle start; it generally is not. You need the second phase.
- Forgetting that 'find the duplicate number' is cycle detection on i -> nums[i], with the duplicate as the cycle entrance.
Interview questions
Quick revision
- slow += 1 step, fast += 2 steps; loop while fast and fast.next.
- Meet = cycle; fast hits None = no cycle.
- Cycle start: reset one to head, both 1 step, meet at start (a = k * c - b).
- Middle: when fast stops, slow is the middle (second middle for even n).
- Cycle length: from the meeting point, walk around once counting.
- Compare nodes with 'is', not values.
- Implicit lists: happy number, find duplicate (i -> nums[i]).
- O(n) time, O(1) space; a hash set gives the same answer with O(n) space.
Check yourself
1. In Floyd's algorithm, why must slow and fast meet if there is a cycle?
2. After slow and fast meet inside a cycle, how do you find the cycle's first node?
3. For the list 1 -> 2 -> 3 -> 4 (no cycle), where is slow when the loop 'while fast and fast.next' ends, starting both at node 1?
4. What is the extra space used by fast and slow cycle detection?
Related
Saved on this device. Create a free account to keep it on every device.
Practise this with Sam
A real mock interview, out loud, with an honest scorecard. Free to start.