Here is Floyd's cycle detection:
function floydCycleDetection(f, start):
slow = start
fast = start
// Phase 1: Detect if cycle exists
while true:
slow = f(slow)
fast = f(f(fast))
if slow == fast:
break
// Phase 2: Find cycle start
slow = start
while slow != fast:
slow = f(slow)
fast = f(fast)
cycleStart = slow
// Phase 3: Find cycle length
length = 1
fast = f(slow)
while fast != slow:
fast = f(fast)
length = length + 1
return (cycleStart, length)
Time: . Space: .