Как обнаружить цикл с помощью алгоритма черепахи и зайца Флойда?

Question

Accepted Answer

**Детектирование цикла Флойда** находит петлю в последовательности (например, в связном списке) с помощью двух указателей, движущихся с разными скоростями. Если цикл существует, быстрый указатель в конце концов нагоняет и встречается с медленным. Алгоритм использует **O(1)** дополнительной памяти.

## Идея

Перемещайте **медленный** указатель на один шаг и **быстрый** указатель на два шага. В цикле разрыв между ними сокращается на один с каждым шагом, поэтому они обязательно встретятся; без цикла быстрый указатель достигает конца.

## Пример

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

## Сложность

- **Время:** O(n). **Память:** O(1).

Подход с хеш-множеством также работает, но требует O(n) памяти; алгоритм Флойда использует константное количество памяти.

## Когда использовать / подводные камни

Используйте для **обнаружения цикла в связном списке**, поиска начала цикла и детектирования циклов в функциональных графах (каждый узел имеет одного преемника). Всегда проверяйте `fast.next`, чтобы избежать разыменования нулевого указателя. Для общих графов вместо этого используйте DFS со стеком рекурсии.

## Почему это важно

Обнаружение циклов критично для безопасного обхода — необнаруженная петля означает бесконечную итерацию.

Алгоритм Флойда — прекрасный пример решения задачи с O(n) памятью в O(1) памяти с помощью хитрого инварианта.

Он часто встречается на собеседованиях по связным спискам и при обнаружении бесконечных циклов в автоматах состояния и числовых последовательностях.