/
Fast & Slow Pointers
Move two pointers at different speeds to detect cycles, find middles, and meet at meaningful positions.
Algorithm Pattern
O(1) Space
What & Why
Floyd's cycle detection — the tortoise and the hare. Move one pointer (slow) one step at a time, and another (fast) two steps at a time. If there's a cycle, they will meet. If fast reaches the end (null), there's no cycle.
The technique generalizes: anywhere you can iterate at different speeds (linked lists, function iteration, number sequences), you can detect cycles, find middles, or solve specific position-relative problems with O(1) extra space.
Visualization
Code (Python)
Python
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
Complexity
| Operation | Time | Space |
|---|---|---|
| Detect cycle | O(n) | O(1) |
| Find middle | O(n) | O(1) |