Как обнаружить цикл в связном списке: алгоритм Флойда «черепаха и заяц»?

Два указателя идут по списку с разной скоростью — «черепаха» на 1 шаг, «заяц» на 2: если цикл есть, заяц догонит черепаху внутри него, если нет — упрётся в `null`; время O(n), память O(1).

Обнаружение

• Без цикла заяц доходит до конца примерно за n/2 итераций.
• С циклом оба указателя в него входят, и расстояние между ними сокращается на 1 за шаг — встреча гарантирована меньше чем за один оборот черепахи.

Поиск начала цикла

1. После встречи верните один указатель в голову.
2. Двигайте оба по одному шагу — встретятся ровно в первом узле цикла.

Почему: пусть a — путь от головы до входа в цикл, b — от входа до точки встречи, c — длина цикла. Заяц прошёл вдвое больше: 2(a + b) = a + b + kc, откуда a = kc − b. Значит, от точки встречи до входа столько же шагов (по модулю c), сколько от головы.

Длина цикла — отметить точку встречи и пройти один оборот, считая шаги.

Альтернативы

• Хеш-множество посещённых узлов: проще, но O(n) памяти.
• Алгоритм Брента: тоже O(1) памяти, обычно меньше вызовов перехода.

Коротко для собеседования

Быстрый и медленный указатели находят цикл за O(n) без дополнительной памяти: если цикл есть, быстрый обязательно догонит медленный. Чтобы найти вход в цикл, после встречи один указатель возвращают в голову и ведут оба по шагу; тот же приём работает для любой функции на конечном множестве, например при поиске дубликата в массиве.