Как можно определить наличие коллизий, используя связный список?

Для определения наличия коллизий (циклов) в связном списке часто используется алгоритм «черепаха и заяц» (Floyd’s Cycle-Finding Algorithm). Идея в том, чтобы использовать два указателя:

• Медленный указатель (черепаха) двигается по одному элементу за шаг.
• Быстрый указатель (заяц) двигается по два элемента за шаг.

Если в списке есть цикл, то быстрый указатель в итоге догонит медленный, и они укажут на один и тот же узел. Если же цикл нет, быстрый указатель достигнет конца списка (null).

Пример на Java:

public boolean hasCycle(ListNode head) {
    ListNode slow = head;
    ListNode fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow == fast) {
            return true; // цикл обнаружен
        }
    }
    return false; // цикла нет
}

Этот метод эффективен и не требует дополнительной памяти.