Come rilevi un ciclo con la tartaruga e la lepre di Floyd?

Question

Accepted Answer

**Floyd's cycle detection** trova un ciclo in una sequenza (come una linked list) usando due puntatori che si muovono a velocità diverse. Se un ciclo esiste, il puntatore veloce raggiunge e incontra quello lento. Usa **O(1)** spazio extra.

## L'idea

Sposta un puntatore **slow** di un passo e un puntatore **fast** di due passi. In un ciclo, il gap si riduce di uno ogni passo, quindi devono collidere; senza un ciclo, il puntatore veloce raggiunge la fine.

## Esempio

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

## Complessità

- **Tempo:** O(n). **Spazio:** O(1).

Un approccio con hash-set funziona ma costa O(n) spazio; Floyd's usa spazio costante.

## Quando usare / insidie

Usa per **rilevamento di cicli in linked list**, trovare l'inizio del ciclo, e rilevare cicli in grafi funzionali (ogni nodo ha un successore). Proteggi sempre `fast.next` per evitare dereference nulli. Per grafi generali, usa DFS con uno stack di ricorsione.

## Perché è importante

Rilevare cicli è essenziale per un attraversamento sicuro — un ciclo non rilevato significa iterazione infinita.

L'algoritmo di Floyd è un bellissimo esempio di risoluzione di un problema O(n)-spazio in O(1) spazio con un'invariante intelligente.

Appare in interviste su linked list e nel rilevamento di cicli infiniti in macchine a stati e sequenze numeriche.