Cum detectezi un ciclu cu metoda broasctei și iepurelui a lui Floyd?

Question

Accepted Answer

**Detecția ciclului Floyd** găsește o buclă într-o secvență (cum ar fi o listă înlănțuită) folosind doi pointeri care se mișcă cu viteze diferite. Dacă există un ciclu, pointerul rapid ajunge în cele din urmă și se întâlnește cu cel lent. Folosește **O(1)** spațiu suplimentar.

## Ideea

Mutați un pointer **lent** un pas și un pointer **rapid** doi pași. Într-un ciclu, intervalul se micșorează cu unu la fiecare pas, deci trebuie să se ciocnească; fără ciclu, pointerul rapid ajunge la capăt.

## Exemplu

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

## Complexitate

- **Timp:** O(n). **Spațiu:** O(1).

O abordare cu hash-set funcționează, dar costă O(n) spațiu; Floyd folosește spațiu constant.

## Când să folosești / probleme

Folosiți pentru **detecția buclei în lista înlănțuită**, găsirea începutului ciclului și detectarea ciclurilor în grafuri funcționale (fiecare nod are un succesor). Protejați întotdeauna `fast.next` pentru a evita dereferențiarea null. Pentru grafuri generale, folosiți DFS cu un stack de recursivitate.

## De ce conteaza

Detectarea ciclurilor este esențială pentru traversare sigură — o buclă nedetectată înseamnă iterație infinită.

Algoritmul Floyd este un exemplu frumos de rezolvare a unei probleme cu O(n) spațiu în O(1) spațiu cu o invariantă inteligentă.

Apare în interviuri despre liste înlănțuite și în detectarea buclelor infinite în mașini de stări și secvențe de numere.