💡 Алгоритм Флойда находит цикл в связном списке всего с двумя указателями и `O(1)` дополнительной памяти.

Идея простая:

slow двигается на 1 узел
fast — на 2

Если цикл есть, они обязательно встретятся.

После встречи один указатель возвращаем в head, а дальше оба двигаем по одному узлу. Следующая точка встречи — точное начало цикла.


Node *detect_cycle(Node *head) {
Node *slow = head, *fast = head;

while (fast && fast->next) {
slow = slow->next;
fast = fast->next->next;

if (slow == fast) {
slow = head;

while (slow != fast) {
slow = slow->next;
fast = fast->next;
}

return slow;
}
}

return NULL;
}

Сложность:


O(n) по времени
O(1) по памяти


Один из самых красивых примеров того, как простая математика по модулю превращается в очень практичный алгоритм.