Fast and Slow Pointers: Detecting Cycles Without Extra Memory

← Back to Blog & Articles

The fast and slow pointer pattern uses two pointers that move through a sequence at different speeds. It is the standard way to detect cycles and find midpoints with constant extra space.

The core idea

Start both pointers at the head. Move the slow pointer one step at a time and the fast pointer two steps at a time. If the structure has a cycle, the fast pointer eventually laps the slow one and they meet. If there is no cycle, the fast pointer reaches the end.

slow = head
fast = head
while fast is not null and fast.next is not null:
    slow = slow.next
    fast = fast.next.next
    if slow == fast:
        return true      # cycle found
return false

Finding where the cycle starts

After the pointers meet, move one pointer back to the head. Advance both one step at a time. They meet again at the first node of the cycle. This works because of the distances involved, and it is worth being able to explain it in an interview.

Finding the midpoint

When the fast pointer reaches the end of a list, the slow pointer is at the middle. This is useful for splitting a list, checking palindromes, and merge sort on linked lists.

Why it beats the alternative

A hash set can also detect cycles by remembering visited nodes, but it uses O(n) extra space. The two-pointer approach uses O(1) space and still runs in O(n) time.

Recognizing the pattern

Look for linked lists, repeated states, or sequences defined by a function that feeds its output back into itself, such as the "happy number" problem. Guard against null pointers by checking both fast and fast.next before moving.

Continue with the book

Explore the full treatment, worked examples, and exercises in Algorithmic Edge.