Floyd Cycle Detection
MediumOne pointer moves twice as fast. If there is a loop they must meet inside it, and resetting one to the head finds where the loop starts.
fast and slowconstant space
TimeO(n)
SpaceO(1)
Inputvalues | index the tail loops back to (-1 for no loop)
slowfast
1
2
3
4
5
6
Both pointers start at the head. The tail loops back to index 2.
steps0
1 / 10
slow = head; fast = head
while fast and fast.next:
slow = slow.next; fast = fast.next.next
if slow == fast: cycle found
// find entry: reset slow to head,
// then advance both one step at a time
Why it matters
A visited set also works but costs O(n) memory, which the interviewer will ban.
Keyboard
space play← → stepr restartctrl K search
More in Linked List
Next visualiser
Merge Two Sorted Lists