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

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

Для эффективного обнаружения циклов разработчики часто используют алгоритм поиска цикла Флойда, также известный как алгоритм черепахи и зайца. . Этот алгоритм использует две ссылки, медленную и быструю, которые перемещаются по списку с разной скоростью.

Например, медленная ссылка продвигается вперед на один узел, а быстрая ссылка — на два узла. Если связанный список содержит цикл, эти ссылки в конечном итоге встретятся. С другой стороны, если цикла нет, либо медленная, либо быстрая ссылка (или их последующие ссылки) станут нулевыми до того, как другая достигнет конца списка.

Вот Java-реализация алгоритма Флойда. :

boolean hasLoop(Node first) {
    if (first == null) {
        return false; // List does not exist, so no loop
    }

    Node slow, fast; // Create two references.
    slow = fast = first; // Make both refer to the start of the list.

    while (true) {
        slow = slow.next; // One hop.

        if (fast.next != null) {
            fast = fast.next.next; // Two hops.
        } else {
            return false; // No loop.
        }

        if (slow == null || fast == null) {
            return false; // No loop.
        }

        if (slow == fast) {
            return true; // Loop detected.
        }
    }
}

Этот алгоритм использует пространственную сложность O(1) и работает за время O(n), что делает его эффективным с точки зрения использования памяти и разумными затратами времени.