Перейти к основному содержимому

Проверка связанного списка на цикличность

· 9 мин. чтения

1. Введение​

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

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

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

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

2.1. Грубая сила — временная сложность 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. Грубая сила​

Как только быстрый и медленный итераторы встречаются в какой-то точке цикла, мы берем еще один итератор (скажем, 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. Как только быстрые и медленные итераторы встретятся, найдите длину цикла. Это можно сделать, оставив один из итераторов на месте, продолжая работу другого итератора (выполняя итерацию с нормальной скоростью, один за другим), пока он не достигнет первого указателя, сохраняя количество посещенных узлов. Это считается как л
  2. Возьмите два итератора ( ptr1 и ptr2 ) в начале списка. Переместить один из шагов итератора ( ptr2 ) l
  3. Теперь повторяйте оба итератора до тех пор, пока они не встретятся в начале цикла, затем найдите конец цикла и укажите его на ноль .

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

И вот простая потенциальная реализация:

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 (точка встречи внутри цикла)

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

к + м * л + у = 2 * (к + у)

который оценивается как:

у = м * л - к

Вычитание обеих сторон из l дает:

л – у = л – м * л + к

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

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

Это ведет к:

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

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

  1. Используйте «Алгоритм поиска цикла Флайода» для обнаружения петли. Если цикл существует, этот алгоритм завершится в точке внутри цикла (назовем это точкой встречи).
  2. Возьмите два итератора, один во главе списка ( it1 ) и один в точке встречи ( it2 )
  3. Перемещайтесь по обоим итераторам с одинаковой скоростью
  4. Поскольку расстояние цикла от головы равно k (как определено выше), итератор, запущенный с головы, достигнет цикла через k шагов .
  5. За k шагов итератор it2 пройдет m – 1 цикл цикла и дополнительное расстояние z. Поскольку этот указатель уже находился на расстоянии z от начала цикла, прохождение этого дополнительного расстояния z приведет к тому, что он также окажется в начале цикла.
  6. Оба итератора встречаются в начале цикла, впоследствии мы можем найти конец цикла и указать на ноль

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

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 .