Wie erkennst du einen Zyklus mit Floyds Schildkröte und Hase?

Question

Accepted Answer

**Floyds Zyklenerkennung** findet eine Schleife in einer Sequenz (wie eine linked list) mithilfe von zwei Zeigern, die sich mit unterschiedlichen Geschwindigkeiten bewegen. Falls ein Zyklus existiert, holt der schnelle Zeiger den langsamen Zeiger schließlich ein und trifft ihn. Es verwendet **O(1)** zusätzlichen Speicher.

## Die Idee

Bewege einen **slow** Zeiger um einen Schritt und einen **fast** Zeiger um zwei Schritte. In einem Zyklus verringert sich die Lücke um eins mit jedem Schritt, daher müssen sie kollidieren; ohne Zyklus erreicht der schnelle Zeiger das Ende.

## Beispiel

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

## Komplexität

- **Zeit:** O(n). **Speicher:** O(1).

Ein Hash-Set-Ansatz funktioniert auch, kostet aber O(n) Speicher; Floyds verwendet konstanten Speicher.

## Wann zu verwenden / Fallstricke

Verwende für **Linked-List-Schleifenerkennung**, Finden des Zyklus-Anfangs und Erkennung von Zyklen in funktionalen Graphen (jeder Knoten hat einen Nachfolger). Schütze immer `fast.next`, um Null-Dereferenzierungen zu vermeiden. Für allgemeine Graphen verwende stattdessen DFS mit einem Rekursions-Stack.

## Warum es wichtig ist

Zyklenerkennung ist unverzichtlich für sicheres Traversieren — eine unerkannte Schleife bedeutet unendliche Iteration.

Floyds Algorithmus ist ein wunderschönes Beispiel für die Lösung eines O(n)-Speicher-Problems in O(1)-Speicher mit einer cleveren Invariante.

Es erscheint in Linked-List-Interviews und beim Erkennen von Endlosschleifen in Zustandsautomaten und Zahlenfolgen.