Bagaimana anda mengesan kitaran dengan penyu dan arnab Floyd?

Question

Accepted Answer

**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.

## Ideanya

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.

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

## Kerumitan

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

Pendekatan set-hash juga berfungsi tetapi memerlukan ruang O(n); Floyd's menggunakan ruang malar.

## Bila digunakan / perangkap

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.

## Mengapa ia penting

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.