Floyd's Cycle Detection
Also known as the "tortoise and hare" algorithm. Use two pointers moving at different speeds - if there's a cycle, they'll eventually meet. Elegant, O(1) space, and works like magic.
The Core Idea
Slow pointer moves one step, fast pointer moves two steps. If there's no cycle, fast reaches the end. If there's a cycle, fast catches up to slow from behind - they'll meet inside the cycle.
If there's a cycle, the fast pointer gains one step on the slow pointer each iteration. They must eventually meet. When they do, reset one to the start and move both at speed 1 - they'll meet at the cycle's start.
Classic: Detect Cycle in Linked List
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return FalseFind the Cycle Start
def detectCycleStart(head):
slow = fast = head
# Find meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
else:
return None # No cycle
# Find cycle start
slow = head
while slow != fast:
slow = slow.next
fast = fast.next
return slow # Cycle starts hereClassic: Find Duplicate Number
Array as linked list - nums[i] points to next index:
def findDuplicate(nums):
slow = fast = nums[0]
# Find meeting point
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Find cycle start (the duplicate)
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowWhen to Use Floyd's Algorithm
- Cycle detection - In linked lists or sequences
- Finding cycle start - Where does the loop begin
- Finding duplicates - Array as implicit linked list
- Happy number - Detect if sequence cycles
Any sequence where each element points to another (like nums[i] → nums[nums[i]]) can be treated as a linked list. Floyd's algorithm works on these implicit lists too.