Floyd's cycle detection mencari gelung dalam jujukan (seperti senarai berpaut) menggunakan dua penunjuk yang bergerak pada kecepatan berbeza. Jika kitaran wujud, penunjuk pantas akhirnya bertemu dengan penunjuk perlahan. Ia menggunakan O(1) ruang tambahan.
Kalihkan penunjuk slow satu langkah dan penunjuk fast dua langkah. Dalam kitaran, jurang berkurang satu setiap langkah, jadi mereka mesti berlanggar; tanpa kitaran, penunjuk pantas mencapai akhir.
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
Pendekatan set-hash juga berfungsi tetapi memerlukan ruang O(n); Floyd's menggunakan ruang malar.
Gunakan untuk pengesan gelung senarai-berpaut, mencari permulaan kitaran, dan mengesan kitaran dalam graf fungsi (setiap nod mempunyai satu pengganti). Sentiasa lindungi fast.next untuk mengelakkan penghapusan nol. Untuk graf umum, gunakan DFS dengan timbunan rekursi.
Mengesan kitaran adalah penting untuk lintasan yang selamat — gelung yang tidak dikesan bermakna lelaran tak terhingga.
Algoritma Floyd adalah contoh indah menyelesaikan masalah O(n)-ruang dalam O(1) ruang dengan invarian yang bijak.
Ia muncul dalam temu duga senarai-berpaut dan dalam pengesanan gelung tak terhingga dalam mesin keadaan dan jujukan nombor.
Pustaka soalan temu duga IT dengan jawapan terperinci — daripada Junior hingga Senior.
Derma