Kako zaznate cikel s Floydovim tehniko želve in zajca?

Question

Accepted Answer

**Floydova zaznava cikla** najde zanko v zaporedju (na primer povezana seznam) z uporabo dveh kazalcev, ki se gibljeta z različnimi hitrostmi. Če cikel obstaja, hitri kazalec sčasoma ujame in se sreča s počasnim. Porabi **O(1)** dodatnega prostora.

## Ideja

Premakni kazalec **slow** za en korak in kazalec **fast** za dva koraka. V ciklu se razdalja zmanjšuje za ena na vsak korak, zato se morata trčiti; brez cikla hitri kazalec doseže konec.

## Primer

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

## Zahtevnost

- **Čas:** O(n). **Prostor:** O(1).

Pristop s hash-setom tudi deluje, vendar stane O(n) prostora; Floydov uporablja konstanten prostor.

## Kdaj uporabiti / pasti

Uporabite za **zaznavo zanke v povezanem seznamu**, iskanje začetka cikla in zaznavo ciklov v funkcijskih grafih (vsako vozlišče ima enega naslednika). Vedno varujte `fast.next`, da se izognete ničelnim referencam. Za splošne grafe namesto tega uporabite DFS s skladom rekurzije.

## Zakaj je pomembno

Zaznava ciklov je bistvena za varno prečkovanje — nezaznana zanke pomenijo neskončno iteracijo.

Floydov algoritem je lep primer reševanja problema O(n)-prostora v O(1) prostoru s pametno invarianto.

Pojavi se pri intervjujih za povezane sezname in pri zaznavanju neskončnih zank v avtomatih stanj in numeričnih zaporedjih.