Floyd-féle ciklusdetekció egy szekvenciában (például egy összekapcsolt listában) talál hurkot két mutató segítségével, amelyek különböző sebességgel mozognak. Ha ciklus létezik, a gyorsabb mutató végül utoléri és találkozik a lassabbikkal. O(1) extra helyet használ.
Mozgasd a slow mutatót egy lépéssel és a fast mutatót két lépéssel. Egy ciklusban a szakadék minden lépésnél eggyel csökken, így ütközniük kell; ciklus nélkül a gyors eléri a végét.
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
A hash-set megközelítés szintén működik, de O(n) helyet igényel; Floyd állandó helyet használ.
Használd az összekapcsolt lista hurok detektálásához, a ciklus kezdetének megtalálásához és ciklus detektálásához funkcionális gráfokban (minden csomópontnak egy utódja van). Mindig védd az fast.next mutatót null dereferencálás elkerülésére. Általános gráfok esetén használj DFS-t rekurziós veremmekkel.
A ciklus detektálása nélkülözhetetlen a biztonságos bejáráshoz — egy nem észrevett hurok végtelennel egyenlő iterációt jelent.
Floyd algoritmusa szép példa egy O(n)-helyes probléma O(1) helyen történő megoldására egy ügyes invariáns segítségével.
Megjelenik az összekapcsolt lista interjúkban és a végtelen hurkok detektálásában az állapotgépekben és a számsorozatokban.