Floyds syklusdeteksjon finner en løkke i en sekvens (som en lenket liste) ved å bruke to pekere som beveger seg med ulik hastighet. Hvis en syklus eksisterer, møtes den raske pekeren til slutt den sakte pekeren. Det bruker O(1) ekstra plass.
Flytt en treg peker ett steg og en rask peker to steg. I en syklus reduseres avstanden med én for hvert steg, så de må kollidere; uten en syklus når den raske pekeren slutten.
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-tilnærming fungerer også, men koster O(n) plass; Floyds bruker konstant plass.
Bruk for syklusdeteksjon i lenket liste, for å finne syklussens start, og for å detektere sykler i funksjonelle grafer (hver node har én etterfølger). Pass alltid på fast.next for å unngå null-derefaranser. For generelle grafer, bruk DFS med en rekursjonsstakk i stedet.
Å detektere sykler er vesentlig for sikker traversering — en uoppdaget løkke betyr uendelig iterasjon.
Floyds algoritme er et vakkert eksempel på å løse et O(n)-plass-problem med O(1) plass ved hjelp av en smart invariant.
Det dukker opp i lenket-list-intervjuer og ved deteksjon av uendelige løkker i tilstandsmaskiner og tallsekvenser.