Kako detektirate ciklus pomoću Floyd-ove kornjače i zeca?

Question

Accepted Answer

**Floyd-ova detekcija ciklusa** pronalazi petlju u nizu (poput povezane liste) koristeći dva pokazivača koji se kreću različitim brzinama. Ako postoji ciklus, brži pokazivač na kraju sustigne i susretne sporiju. Koristi **O(1)** dodatnog prostora.

## Ideja

Pomakni **slow** pokazivač za jedan korak i **fast** pokazivač za dva koraka. U ciklusu se praznina smanjuje za jedan svaki korak, pa se moraju sudariti; bez ciklusa, brži dostiže kraj.

## Primjer

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

## Složenost

- **Vrijeme:** O(n). **Prostor:** O(1).

Pristup s hash-skupom također radi, ali košta O(n) prostora; Floyd-ov koristi konstantan prostor.

## Kada koristiti / zamke

Koristi za **detekciju petlje povezane liste**, pronalaženje početka ciklusa i detekciju ciklusa u funkcionalnim grafovima (svaki čvor ima jednog nasljednika). Uvijek zaštiti `fast.next` kako bi se izbjeglo dereferenciranje null. Za opće grafove, koristi DFS sa stekom rekurzije.

## Zašto je bitno

Detekcija ciklusa je neophodna za sigurnu traversu — neotkriven petlja znači beskonačnu iteraciju.

Floyd-ov algoritam je lijep primjer rješavanja O(n)-prostora problema u O(1) prostoru s pametnom invarijantom.

Pojavljuje se u intervjuima za povezane liste i u detekciji beskonačnih petlji u automatima stanja i brojevnim nizovima.