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

1. введение

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

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

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

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

2.1. Грубая сила – O(n^2) Временная сложность

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

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

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

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

        int x = nodesTraversedByOuter;
        Node 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)

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

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

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

    Set> set = new HashSet<>();
    Node 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. Быстрые и медленные указатели

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

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

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

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

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

    Node slow = head;
    Node 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 – это класс удобства для хранения результата: переменная boolean , которая указывает, существует ли цикл или нет, и если существует, то это также содержит ссылку на точку встречи внутри цикла:

public class CycleDetectionResult {
    boolean cycleExists;
    Node node;
}

Этот метод также известен как “Алгоритм черепахи и Зайца” или “Алгоритм поиска циклов Флойда”.

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

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

3.1. Грубая сила

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

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

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

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

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

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

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

        return false;
    }

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

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

        loopStart.next = null;
    }
}

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

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

Давайте сначала определим несколько переменных:

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

У нас есть следующая связь между этими переменными: k +

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

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

Как только быстрые и медленные итераторы встретятся, найдите длину цикла. Это можно сделать, удерживая один из итераторов на месте, продолжая другой итератор (итерацию с нормальной скоростью, один за другим), пока он не достигнет первого указателя, сохраняя количество посещенных узлов. Это считается как долго
Возьмите два итератора ( ptr1 и ptr2 ) в начале списка. Переместите один из итераторов ( ptr2 ) l шагов
Теперь повторите оба итератора, пока они не встретятся в начале цикла, затем найдите конец цикла и укажите его на null

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

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

public class CycleRemovalByCountingLoopNodes {
    private static  void removeCycle(
      Node loopNodeParam, Node head) {
        int cycleLength = calculateCycleLength(loopNodeParam);
        Node cycleLengthAdvancedIterator = head;
        Node 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  int calculateCycleLength(
      Node loopNodeParam) {
        Node loopNode = loopNodeParam;
        int length = 1;

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

        return length;
    }
}

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

3.3. Оптимизированное решение – Без учета узлов цикла

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

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

y точки, в которой встречаются два итератора, как видно из начала цикла
z of the point where the two iterators meet, as seen from the end of the cycle (this is also equal to//l-у ) m
раз, когда быстрый итератор завершил цикл, прежде чем медленный итератор войдет в цикл

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

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

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

к + М * Л + * (К + у)

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

И * Л-к

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

l – – m * l + k

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

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

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

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

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

Используйте “Алгоритм поиска циклов Флойда” для обнаружения цикла. Если цикл существует, этот алгоритм закончится в точке внутри цикла (назовите это точкой встречи)
Возьмите два итератора, один в начале списка ( it 1 ) и один в месте встречи ( it 2 )
Пройдите оба итератора с одинаковой скоростью
Поскольку расстояние цикла от head risk (как определено выше), итератор, запущенный из head, достигнет цикла после k шагов
В k шагах итератор it2 пересечет m – 1 циклы цикла и дополнительное расстояние z. Поскольку этот указатель уже находился на расстоянии z от начала цикла, пересечение этого дополнительного расстояния z приведет его также в начало цикла
Оба итератора встречаются в начале цикла, впоследствии мы можем найти конец цикла и указать его на null

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

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

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

        loopNode.next = null;
    }
}

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

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

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

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

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