Обнаружение циклов в связном списке в Java

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

Вот пример такой структуры:

class Node {
    Node next;
    // some user data
}

В этом случае может возникнуть необходимость написания функции boolean hasLoop(Node first), которая возвращает true, если данный узел является первым в списке с циклом, и false в противном случае.

Алгоритм Флойда (Заяц и Черепаха)

Один из самых эффективных способов обнаружения циклов в связном списке — это алгоритм Флойда, также известный как алгоритм «заяц и черепаха».

Алгоритм работает следующим образом:

1. Создаются два указателя, один из которых перемещается вдвое быстрее другого.
2. Если в списке нет цикла, более быстрый указатель достигнет конца списка раньше медленного указателя.
3. Если в списке есть цикл, быстрый указатель «обгонит» медленный указатель внутри цикла.

Вот пример функции hasLoop с использованием этого алгоритма:

boolean hasLoop(Node first) {
    if (first == null) { // список пустой
        return false;
    }

    Node slow, fast; // создаем два указателя

    slow = fast = first;

    while(true) {
        slow = slow.next;          // 1 шаг за раз

        if(fast.next != null)
            fast = fast.next.next; // 2 шага за раз
        else
            return false;          // следующий узел пустой, значит список закончился

        if(slow == null || fast == null) // если узел пустой, значит список закончился
            return false;

        if(slow == fast) // если два указателя встретились, значит есть цикл
            return true;
    }
}

Таким образом, можно эффективно обнаружить наличие цикла в связном списке, используя константное количество памяти и разумное количество времени.