Kuinka havaitset syklin Floydin kilpikonnan ja jäniksen avulla?

Question

Accepted Answer

**Floydin syklin havaitseminen** löytää silmukan sekvenssistä (kuten linkitetystä listasta) käyttämällä kahta osoitinta, jotka liikkuvat eri nopeuksilla. Jos sykli on olemassa, nopea osoitin lopulta saavuttaa hitaan osoittimen ja kohtaa sen. Se käyttää **O(1)** ylimääräistä muistia.

## Idea

Liikuta **slow** osoitinta yhden askeleen ja **fast** osoitinta kahden askeleen. Syklissä aukko kutistuu yhdellä jokaisessa askeleessa, joten ne on pakko törmätä; ilman sykliä nopea osoitin saavuttaa loppun.

## Esimerkki

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

## Monimutkaisuus

- **Aika:** O(n). **Muisti:** O(1).

Hash-joukkoon perustuva lähestymistapa toimii myös, mutta maksaa O(n) muistia; Floydin käyttää vakiomuistia.

## Milloin käyttää / Sudenkuopat

Käytä **linkitetyn listan silmukan havaitsemiseen**, syklin alun löytämiseen ja syklien havaitsemiseen funktionaalisissa graafeissa (jokaisella solmulla on yksi seuraaja). Aina suojaa `fast.next` nolla-dereference-virheiden välttämiseksi. Yleisille graafeille käytä sen sijaan DFS-algoritmiä rekursiopynnöllä.

## Miksi se on tärkeä

Syklin havaitseminen on välttämätöntä turvalliselle käyttöjäärjestykselle — havaittu silmukka tarkoittaa ääretöntä iteraatiota.

Floydin algoritmi on kaunis esimerkki O(n)-muistiongelman ratkaisemisesta O(1)-muistissa älykkään invariantin avulla.

Se ilmestyy linkitetyn listan haastatteluissa ja äärettömien silmukoiden havaitsemisessa tilakoneiden ja numerojonojen yhteydessä.