Cycle Detection
O(n) SpaceO(1) Picture two runners on a circular track. One runs twice as fast as the other. If the track is a loop, the fast runner will eventually lap the slow one and they’ll meet. If the track is a straight line, the fast runner just reaches the end. Meeting = cycle. No meeting = no cycle.
When to use it: Detecting cycles in linked lists, finding duplicate numbers in arrays (Floyd’s algorithm), or determining if a sequence of function applications enters a cycle.
Key insight: If a cycle exists, the fast pointer (moving 2 steps) will eventually catch the slow pointer (moving 1 step) inside the cycle. To find where the cycle starts, reset one pointer to the head and move both at speed 1 — they meet at the cycle entrance.
Common trap: Forgetting to find the cycle start after detecting it. Many problems need the entry point, not just a boolean “cycle exists.”
function hasCycle(head):
slow = head
fast = head
while fast != null and fast.next != null:
slow = slow.next # move 1 step
fast = fast.next.next # move 2 steps
if slow == fast:
return true # they met inside the cycle
return false # fast reached the end, no cycle
function findCycleStart(head):
slow = head
fast = head
# Phase 1: Detect cycle
while fast != null and fast.next != null:
slow = slow.next
fast = fast.next.next
if slow == fast:
break
if fast == null or fast.next == null:
return null # no cycle
# Phase 2: Find entry point
slow = head # reset slow to head
while slow != fast:
slow = slow.next # both move at speed 1
fast = fast.next
return slow # meeting point is cycle startclass ListNode:
def __init__(self, val: int = 0, next: "ListNode | None" = None):
self.val = val
self.next = next
def has_cycle(head: ListNode | None) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
def find_cycle_start(head: ListNode | None) -> ListNode | None:
slow = fast = head
# Phase 1: Detect cycle
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: Find entry point
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
def find_duplicate(nums: list[int]) -> int:
"""Find the duplicate in [1..n] array with n+1 elements (Floyd's)."""
slow = fast = nums[0]
# Phase 1: Find meeting point
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: Find entrance
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slowProblem: Given an array of n+1 integers where each integer is between 1 and n inclusive, find the one duplicate number without modifying the array and using only O(1) extra space.
How would you approach this?
Answer: This is Floyd's cycle detection applied to an array. Treat each value as a pointer to the next index: next = nums[current]. A duplicate means two indices point to the same place, creating a cycle. Find the cycle entrance using the two-phase algorithm.
Problem: Given the head of a linked list, return the node where the cycle begins. If there is no cycle, return null.
How would you approach this?
Answer: This is Floyd's tortoise and hare. Phase 1: slow (1 step) and fast (2 steps) detect the cycle by meeting. Phase 2: reset slow to head, move both at speed 1 — they meet at the cycle entrance.
Time: O(n) because the slow pointer traverses at most the entire list, and the fast pointer makes at most two full traversals. Once inside the cycle, the fast pointer catches the slow pointer within one full cycle length.
Space: O(1) because only two pointer variables are used. This is the key advantage over using a hash set (which would be O(n) space).