Jak zjistíte cyklus pomocí Floydova algoritmu želvy a zajíce?

Question

Accepted Answer

**Detekce cyklu Floyda** najde smyčku v posloupnosti (například v propojeném seznamu) pomocí dvou ukazatelů, které se pohybují různými rychlostmi. Pokud cyklus existuje, rychlý ukazatel nakonec doběhne a setká se s pomalým. Využívá **O(1)** dodatečné paměti.

## Myšlenka

Posunujte **slow** ukazatel o jeden krok a **fast** ukazatel o dva kroky. V cyklu se mezera zmenšuje o jednu v každém kroku, takže se musí srazit; bez cyklu rychlý ukazatel dosáhne konce.

## Příklad

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

- **Čas:** O(n). **Paměť:** O(1).

Přístup s hash-set také funguje, ale stojí O(n) paměti; Floydův algoritmus používá konstantní paměť.

## Kdy použít / Úskalí

Používejte pro **detekci smyček v propojeném seznamu**, hledání začátku cyklu a detekci cyklů v funkčních grafech (každý uzel má jednoho následníka). Vždy chráňte `fast.next`, aby se zabránilo null dereferencím. Pro obecné grafy použijte místo toho DFS s rekurzivním stackem.

## Proč je to důležité

Detekce cyklů je nezbytná pro bezpečné procházení — nedetekovaná smyčka znamená nekonečnou iteraci.

Floydův algoritmus je krásný příklad řešení problému s O(n) pamětí v O(1) paměti pomocí chytrého invariantu.

Objevuje se v rozhovorech o propojeném seznamu a při detekci nekonečných smyček v stavových automatech a číselných posloupnostech.