«1. Введение

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

В большинстве случаев мы хотим иметь возможность обнаруживать и знать об этих циклах; эта статья будет посвящена именно этому — обнаружению и потенциальному удалению циклов.

2. Обнаружение цикла

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

2.1. Brute Force — временная сложность O(n^2)

С помощью этого алгоритма мы проходим по списку, используя два вложенных цикла. Во внешнем цикле мы проходим один за другим. Во внутреннем цикле мы начинаем с головы и проходим столько узлов, сколько за это время пройдено внешним циклом.

Если узел, который посещается внешним циклом, дважды посещается внутренним циклом, то обнаружен цикл. И наоборот, если внешний цикл достигает конца списка, это подразумевает отсутствие циклов: 

public static <T> boolean detectCycle(Node<T> head) {
    if (head == null) {
        return false;
    }

    Node<T> it1 = head;
    int nodesTraversedByOuter = 0;
    while (it1 != null && it1.next != null) {
        it1 = it1.next;
        nodesTraversedByOuter++;

        int x = nodesTraversedByOuter;
        Node<T> it2 = head;
        int noOfTimesCurrentNodeVisited = 0;

        while (x > 0) {
            it2 = it2.next;

            if (it2 == it1) {
                noOfTimesCurrentNodeVisited++;
            }

            if (noOfTimesCurrentNodeVisited == 2) {
                return true;
            }

            x--;
        }
    }

    return false;
}

Преимущество этого подхода в том, что он требует постоянного объема памяти. Недостатком является то, что производительность очень низкая, когда в качестве входных данных предоставляются большие списки.

2.2. Хеширование — O(n) пространственная сложность

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

Когда мы встречаем узел, который уже существует в наборе, мы бы обнаружили начало цикла. Обнаружив это, мы можем легко разорвать цикл, установив для следующего поля предыдущего узла значение null, как показано ниже: 

public static <T> boolean detectCycle(Node<T> head) {
    if (head == null) {
        return false;
    }

    Set<Node<T>> set = new HashSet<>();
    Node<T> node = head;

    while (node != null) {
        if (set.contains(node)) {
            return true;
        }
        set.add(node);
        node = node.next;
    }

    return false;
}

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

2.3. Быстрые и медленные указатели

Следующий алгоритм поиска циклов лучше всего объяснить с помощью метафоры.

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

Здесь мы используем аналогичный подход, перебирая список одновременно с медленным итератором (удвоенная скорость). Как только оба итератора вошли в цикл, они в конце концов встретятся в одной точке.

Следовательно, если два итератора встречаются в какой-либо точке, мы можем заключить, что наткнулись на цикл: 

public static <T> CycleDetectionResult<T> detectCycle(Node<T> head) {
    if (head == null) {
        return new CycleDetectionResult<>(false, null);
    }

    Node<T> slow = head;
    Node<T> fast = head;

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

        if (slow == fast) {
            return new CycleDetectionResult<>(true, fast);
        }
    }

    return new CycleDetectionResult<>(false, null);
}

Где CycleDetectionResult — это вспомогательный класс для хранения результата: существует или нет, и если существует, то это также содержит ссылку на точку встречи внутри цикла: 

public class CycleDetectionResult<T> {
    boolean cycleExists;
    Node<T> node;
}

Этот метод также известен как «Алгоритм Черепахи и Зайца» или «Цикл Флайодса». -Алгоритм поиска».

3. Удаление циклов из списка

Давайте рассмотрим несколько способов удаления циклов. Все эти методы предполагают, что «Алгоритм поиска цикла Флайода» использовался для обнаружения цикла и построения на его основе.

3.1. Brute Force

Как только быстрый и медленный итераторы встречаются в какой-то точке цикла, мы берем еще один итератор (скажем, ptr) и указываем его на начало списка. Мы начинаем перебирать список с ptr. На каждом этапе мы проверяем, доступен ли ptr из точки встречи.

Это завершается, когда ptr достигает начала цикла, потому что это первая точка, когда он входит в цикл и становится доступным из точки встречи.

Как только начало цикла (bg) обнаружено, найти конец цикла (узел, следующее поле которого указывает на bg) просто. Затем следующий указатель этого конечного узла устанавливается равным нулю, чтобы удалить цикл: 

public class CycleRemovalBruteForce {
    private static <T> void removeCycle(
      Node<T> loopNodeParam, Node<T> head) {
        Node<T> it = head;

        while (it != null) {
            if (isNodeReachableFromLoopNode(it, loopNodeParam)) {
                Node<T> loopStart = it;
                findEndNodeAndBreakCycle(loopStart);
                break;
            }
            it = it.next;
        }
    }

    private static <T> boolean isNodeReachableFromLoopNode(
      Node<T> it, Node<T> loopNodeParam) {
        Node<T> loopNode = loopNodeParam;

        do {
            if (it == loopNode) {
                return true;
            }
            loopNode = loopNode.next;
        } while (loopNode.next != loopNodeParam);

        return false;
    }

    private static <T> void findEndNodeAndBreakCycle(
      Node<T> loopStartParam) {
        Node<T> loopStart = loopStartParam;

        while (loopStart.next != loopStartParam) {
            loopStart = loopStart.next;
        }

        loopStart.next = null;
    }
}

К сожалению, этот алгоритм также плохо работает в случае больших списков и больших циклов, потому что нам приходится проходить цикл несколько раз.

«3.2. Оптимизированное решение — подсчет узлов цикла

Сначала определим несколько переменных:

    n = размер списка k = расстояние от начала списка до начала цикла l = размер цикл

Мы имеем следующую связь между этими переменными: k + l = n

Мы используем эту связь в этом подходе. В частности, если итератор, начинающийся с начала списка, уже прошел l узлов, то ему нужно пройти еще k узлов, чтобы достичь конца списка.

Вот схема алгоритма:

  1. Once fast and the slow iterators meet, find the length of the cycle. This can be done by keeping one of the iterators in place while continuing the other iterator (iterating at normal speed, one-by-one) till it reaches the first pointer, keeping the count of nodes visited. This counts as l
  2. Take two iterators (ptr1 and ptr2) at the beginning of the list. Move one of the iterator (ptr2) l steps
  3. Now iterate both the iterators until they meet at the start of the loop, subsequently, find the end of the cycle and point it to null

Это работает, потому что ptr1 находится на k шагов от цикла, а ptr2, который продвигается на l шагов, также нуждается в k шагов, чтобы достичь конца цикла (n – l = к).

А вот и простая возможная реализация: 

public class CycleRemovalByCountingLoopNodes {
    private static <T> void removeCycle(
      Node<T> loopNodeParam, Node<T> head) {
        int cycleLength = calculateCycleLength(loopNodeParam);
        Node<T> cycleLengthAdvancedIterator = head;
        Node<T> it = head;

        for (int i = 0; i < cycleLength; i++) {
            cycleLengthAdvancedIterator 
              = cycleLengthAdvancedIterator.next;
        }

        while (it.next != cycleLengthAdvancedIterator.next) {
            it = it.next;
            cycleLengthAdvancedIterator 
              = cycleLengthAdvancedIterator.next;
        }

        cycleLengthAdvancedIterator.next = null;
    }

    private static <T> int calculateCycleLength(
      Node<T> loopNodeParam) {
        Node<T> loopNode = loopNodeParam;
        int length = 1;

        while (loopNode.next != loopNodeParam) {
            length++;
            loopNode = loopNode.next;
        }

        return length;
    }
}

Далее давайте сосредоточимся на методе, в котором мы можем даже исключить этап вычисления длины цикла.

3.3. Оптимизированное решение — без подсчета узлов цикла

Давайте математически сравним расстояния, пройденные быстрыми и медленными указателями.

Для этого нам понадобятся еще несколько переменных:

    y = расстояние от точки, где встречаются два итератора, как видно из начала цикла z = расстояние от точки, где встречаются два итератора, как видно от конца цикла (это также равно l – y) m = количество раз, когда быстрый итератор завершил цикл до того, как медленный итератор войдет в цикл

Сохранение других переменных такими же, как определено в предыдущем разделе , уравнения расстояния будут определены как:

    Расстояние, пройденное медленным указателем = k (расстояние цикла от головы) + y (точка встречи внутри цикла) Расстояние, пройденное быстрым указателем = k (расстояние цикла от головы) + m (количество раз, когда быстрый указатель завершил цикл до входа медленного указателя) * l (длина цикла) + y (точка встречи внутри цикла)

Мы знаем, что расстояние, пройденное быстрым указателем, в два раза больше, чем расстояние, пройденное медленным указателем, следовательно:

k + m * l + y = 2 * (k + y)

что дает:

y = m * l – k

Вычитание обеих частей из l дает: ~ ~~ l – y = l – m * l + k

или эквивалентно:

k = (m – 1) * l + z (где l – y – это z как определено выше)

Это приводит к:

k = (m – 1) выполняется полный цикл + дополнительное расстояние z

Другими словами, если мы сохраняем один итератор во главе списка, а другой итератор в точке встречи и перемещайте их с той же скоростью, тогда второй итератор совершит m — 1 циклов по циклу и встретится с первым указателем в начале цикла. Используя это понимание, мы можем сформулировать алгоритм:

Это может быть реализовано:

  1. Use ‘Flyods Cycle-Finding Algorithm’ to detect the loop. If loop exists, this algorithm would end at a point inside the loop (call this the meeting point)
  2. Take two iterators, one at the head of the list (it1) and one at the meeting point (it2)
  3. Traverse both iterators at the same speed
  4. Since the distance of the loop from head is k (as defined above), the iterator started from head would reach the cycle after k steps
  5. In k steps, iterator it2 would traverse m – 1 cycles of the loop and an extra distance z. Since this pointer was already at a distance of z from the beginning of the cycle, traversing this extra distance z, would bring it also at the beginning of the cycle
  6. Both the iterators meet at the beginning of the cycle, subsequently, we can find the end of the cycle and point it to null

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

public class CycleRemovalWithoutCountingLoopNodes {
    private static <T> void removeCycle(
      Node<T> meetingPointParam, Node<T> head) {
        Node<T> loopNode = meetingPointParam;
        Node<T> it = head;

        while (loopNode.next != it.next) {
            it = it.next;
            loopNode = loopNode.next;
        }

        loopNode.next = null;
    }
}

4. Заключение

В этой статье мы описали различные алгоритмы обнаружения цикла в списке. Мы рассмотрели алгоритмы с различными требованиями к времени вычислений и объему памяти.

Наконец, мы также показали три метода удаления цикла после его обнаружения с помощью «Алгоритма поиска цикла Флайода».

Полный пример кода доступен на Github.

«