The fast and slow pointer pattern, often called Floyd’s tortoise and hare, moves two pointers through a sequence at different speeds. The slow pointer advances one step at a time while the fast pointer advances two. If the structure contains a cycle, the fast pointer eventually laps the slow one and they meet. If there is no cycle, the fast pointer simply runs off the end.
When to use it#
Use this pattern on linked lists or on sequences defined by a “next” function, especially when the problem mentions cycles, loops, or finding the middle. It is also the standard tool for problems framed as an implicit functional graph, where each value points to exactly one next value, such as the happy number problem. The giveaway is needing to detect repetition without extra space.
Worked example#
Detecting whether a linked list has a cycle:
1def has_cycle(head):
2 slow = fast = head
3 while fast and fast.next:
4 slow = slow.next
5 fast = fast.next.next
6 if slow is fast:
7 return True
8 return False
To find the midpoint of a list instead, run the same loop and return slow when fast reaches the end. To find where a cycle begins, reset one pointer to the head after the meeting point and advance both one step at a time until they meet again.
Complexity#
Time is O(n) because the pointers traverse the structure a constant number of times. Space is O(1), which is the main advantage over hashing visited nodes.
Practice problems#
- Linked List Cycle I and II
- Middle of the Linked List
- Happy Number
- Find the Duplicate Number
- Palindrome Linked List
- Reorder List
This pattern is a specialized cousin of the general two-pointer approach covered in the two pointer technique. Return to the pattern hub for the full map.