Floyds cykeldetektering hittar en loop i en sekvens (som en länkad lista) med hjälp av två pekare som rör sig med olika hastigheter. Om en cykel finns, når den snabba pekaren så småningom och möter den långsamma. Den använder O(1) extra utrymme.
Flytта en slow-pekare ett steg och en fast-pekare två steg. I en cykel minskar gapet med ett varje steg, så de måste kollidera; utan en cykel når fast slutet.
def has_cycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # +1 step
fast = fast.next.next # +2 steps
if slow is fast: # pointers met -> cycle
return True
return False # fast hit the end -> no cycle
En hash-set-metod fungerar också men kostar O(n) utrymme; Floyds använder konstant utrymme.
Använd för cykeldetektering i länkad lista, för att hitta cykelns början och för att detektera cykler i funktionella grafer (varje nod har en efterföljare). Skydda alltid fast.next för att undvika null-referenser. För allmänna grafer använd DFS med en rekursionsstapel istället.
Cykeldetektering är väsentlig för säker traversering — en opdagad loop betyder oändlig iteration.
Floyds algoritm är ett vackert exempel på att lösa ett O(n)-utrymmesproblem på O(1) utrymme med en smart invariant.
Det förekommer i intervjuer om länkade listor och vid detektering av oändliga loopar i tillståndsautomater och talsekvenser.