Поиск цикла

Когда список перестаёт заканчиваться

В корректной обычной цепочке последовательные переходы по next в конце приводят к null. Но если какой-то узел ссылается на уже встречавшийся узел, образуется цикл: простой обход больше никогда не достигнет конца.

Хранить все посещённые узлы в наборе можно, но для односвязного списка есть решение с O(1) дополнительной памяти — алгоритм Флойда с быстрым и медленным указателями.

Алгоритм Флойда

Node slow = head;
Node fast = head;

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow == fast) {
        return true;
    }
}

return false;

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

Почему сравниваются ссылки

Для обнаружения цикла важно сравнивать сами узлы через slow == fast, а не их значения. В списке вполне могут существовать разные узлы с одинаковым value — это не означает, что обход вернулся в уже посещённую позицию.

Оба указателя совершают линейное число шагов, поэтому время работы — O(n), а дополнительная память остаётся O(1).