Floyd's cycle detection algorithm finds a loop in a linked list using just two pointers and O(1) extra space
one pointer moves one node at a time while the other moves two
if a cycle exists they are guaranteed to meet
after they meet reset one pointer to the head and move both one step at a time
the node where they meet again is the exact start of the cycle
one elegant proof from modular arithmetic powers one of the most famous linked list algorithms ever written
English
