Hoe detecteer je een cyclus met Floyd's schildpad en haas?

Question

Accepted Answer

**Floyd's cyclus-detectie** vindt een lus in een reeks (zoals een gekoppelde lijst) met behulp van twee aanwijzers die met verschillende snelheden bewegen. Als een cyclus bestaat, haalt de snelle aanwijzer uiteindelijk de langzame in en ontmoet deze. Het gebruikt **O(1)** extra ruimte.

## Het idee

Beweeg een **langzame** aanwijzer één stap en een **snelle** aanwijzer twee stappen. In een cyclus wordt de afstand tussen hen elke stap met één kleiner, dus ze moeten botsen; zonder een cyclus bereikt de snelle aanwijzer het einde.

## Voorbeeld

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

## Complexiteit

- **Tijd:** O(n). **Ruimte:** O(1).

Een hash-set-aanpak werkt ook maar kost O(n) ruimte; Floyd's gebruikt constante ruimte.

## Wanneer te gebruiken / valkuilen

Gebruik voor **cyclus-detectie in gekoppelde lijsten**, het vinden van het begin van de cyclus, en het detecteren van cycli in functionele grafieken (elk knooppunt heeft één opvolger). Beveilig altijd `fast.next` om null-verwijzingen te vermijden. Voor algemene grafieken, gebruik in plaats daarvan DFS met een recursie-stack.

## Waarom het belangrijk is

Cyclus-detectie is essentieel voor veilige traversal — een niet-gedetecteerde lus betekent oneindige iteratie.

Floyd's algoritme is een mooi voorbeeld van het oplossen van een O(n)-ruimte-probleem in O(1) ruimte met een slimmige invariant.

Het verschijnt in interviews over gekoppelde lijsten en in het detecteren van oneindige lussen in state machines en getallenreeksen.