Jak wykryć cykl za pomocą algorytmu Floyda tortoise and hare?

Question

Accepted Answer

**Detekcja cyklu Floyda** znajduje pętlę w sekwencji (takiej jak lista powiązana) za pomocą dwóch wskaźników poruszających się z różnymi prędkościami. Jeśli cykl istnieje, szybki wskaźnik ostatecznie wyprzedza i spotyka powolny. Algorytm używa **O(1)** dodatkowej pamięci.

## Idea

Przesuń wskaźnik **powolny** o jeden krok i wskaźnik **szybki** o dwa kroki. W cyklu luka zmniejsza się o jeden w każdym kroku, więc muszą się spotkać; bez cyklu szybki wskaźnik osiąga koniec.

## Przykład

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

## Złożoność

- **Czas:** O(n). **Pamięć:** O(1).

Podejście oparte na hash-set również działa, ale kosztuje O(n) pamięci; algorytm Floyda używa stałej pamięci.

## Kiedy używać / pułapki

Używaj do **detekcji pętli w liście powiązanej**, znajdowania początku cyklu i wykrywania cykli w grafach funkcyjnych (każdy węzeł ma jednego następcę). Zawsze strzeż `fast.next`, aby uniknąć dereferencji pustych wskaźników. W przypadku grafów ogólnych użyj zamiast tego DFS ze stosem rekursji.

## Dlaczego to ważne

Wykrywanie cykli jest niezbędne do bezpiecznego przechodzenia — niewykryty cykl oznacza nieskończoną iterację.

Algorytm Floyda jest pięknym przykładem rozwiązania problemu O(n)-space w O(1) space dzięki sprytnej niezmiennikowi.

Pojawiają się w rozmowach kwalifikacyjnych dotyczących list powiązanych oraz w wykrywaniu nieskończonych pętli w maszynach stanów i sekwencjach liczbowych.