Hvordan detekterer du en cyklus ved hjælp af Floyds skildpadde og hare?

Question

Accepted Answer

**Floyds cykeldetection** finder en løkke i en sekvens (som en linked list) ved hjælp af to pointere, der bevæger sig med forskellige hastigheder. Hvis en cyklus findes, når den hurtige pointer til sidst og møder den langsomme pointer. Det bruger **O(1)** ekstra plads.

## Ideen

Flyt en **slow** pointer et trin og en **fast** pointer to trin. I en cyklus krympes gapet med en for hvert trin, så de må kollidere; uden en cyklus når den hurtige pointer slutningen.

## Eksempel

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

## Kompleksitet

- **Tid:** O(n). **Plads:** O(1).

En hash-set tilgang fungerer også, men koster O(n) plads; Floyds bruger konstant plads.

## Hvornår skal du bruge det / Faldgruber

Brug til **linked-list løkkedetection**, find cykelens start og detekter cykler i funktionelle grafer (hver node har en efterfølger). Beskyt altid `fast.next` for at undgå null dereferences. For generelle grafer, brug DFS med en rekursionsstak i stedet.

## Hvorfor det betyder noget

Cykeldetection er vigtig for sikker traversering — en udetekteret løkke betyder uendelig iteration.

Floyds algoritme er et smukt eksempel på at løse et O(n)-plads problem i O(1) plads med en klog invariant.

Det optræder i linked-list interviews og ved detektering af uendelige løkker i tilstandsmaskiner og talsekvenser.