Bagaimana Anda mendeteksi siklus dengan kura-kura dan kelinci Floyd?

Question

Accepted Answer

**Deteksi siklus Floyd** menemukan loop dalam urutan (seperti daftar tertaut) menggunakan dua pointer yang bergerak dengan kecepatan berbeda. Jika siklus ada, pointer cepat akhirnya melampaui dan bertemu yang lambat. Ini menggunakan **O(1)** ruang tambahan.

## Idenya

Pindahkan pointer **slow** satu langkah dan pointer **fast** dua langkah. Dalam siklus, celah menyusut satu per langkah, jadi mereka harus bertabrakan; tanpa siklus, cepat mencapai akhir.

## Contoh

```python
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
```

## Kompleksitas

- **Waktu:** O(n). **Ruang:** O(1).

Pendekatan hash-set juga bekerja tetapi menghabiskan O(n) ruang; Floyd menggunakan ruang konstan.

## Kapan digunakan / perangkap

Gunakan untuk **deteksi loop daftar tertaut**, menemukan awal siklus, dan mendeteksi siklus dalam grafik fungsional (setiap node memiliki satu penerus). Selalu lindungi `fast.next` untuk menghindari dereference null. Untuk grafik umum, gunakan DFS dengan tumpukan rekursi.

## Mengapa ini penting

Mendeteksi siklus sangat penting untuk traversal yang aman — loop yang tidak terdeteksi berarti iterasi tak terbatas.

Algoritma Floyd adalah contoh indah menyelesaikan masalah O(n)-ruang dalam O(1) ruang dengan invarian yang cerdas.

Muncul dalam wawancara daftar tertaut dan dalam mendeteksi loop tak terbatas dalam mesin status dan urutan angka.