Kaip aptikti ciklą naudojant Floyd'o žalią ir kiškį?

Question

Accepted Answer

**Floyd's cycle detection** randa kilpą sekoje (pvz., susigtame sąraše) naudodama du rodiklius, judančius skirtingais greičiais. Jei ciklas yra, greitas rodiklis galiausiai pasiveja lėtą rodiklį. Naudoja **O(1)** papildomo atminties.

## Idėja

Judinkite **slow** rodiklį vienu žingsniu ir **fast** rodiklį dviem žingsniais. Cikle atotrūkis mažėja vienu per žingsnį, todėl jie privalo susidūrti; be ciklo, greitas rodiklis pasiekia pabaigą.

## Pavyzdys

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

## Sudėtingumas

- **Laikas:** O(n). **Atmintis:** O(1).

Žeimės aibės metodas taip pat veikia, tačiau kainuoja O(n) atmintį; Floyd'as naudoja nuolatinę atmintį.

## Kada naudoti / pinkles

Naudokite **susigtų sąrašų kilpos aptikimui**, kilpos pradžios radimui ir ciklų aptikimui funkcinėse diagramose (kiekvienas mazgas turi vieną įpėdinį). Visada apsaugokite `fast.next`, kad išvengtumėte nulinio dereferenciavimo. Bendroms diagramoms naudokite DFS su rekursijos skaitinymu.

## Kodėl tai svarbu

Ciklų aptikimas yra naudingas saugiai peržvalgai — neaptiktas kilpa reiškia begalinę iteraciją.

Floyd'o algoritmas yra puikus O(n)-atminties problemos sprendimo pavyzdys per O(1) atmintį su gudria invariante.

Jis pasirodo susigtų sąrašų pokalbiuose ir begalinių kilpų aptikime būsenose ir skaičių sekose.