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

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

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

В C++ существует множество способов поиска циклов в связанном списке:

Подход на основе хэш-таблицы : этот подход сохраняет адреса посещенных узлов в хэш-таблице. Цикл в связанном списке существует, если узел уже присутствует в хэш-таблице при повторном посещении.

Циклический подход Флойда : Алгоритм «черепаха и заяц», широко известный как алгоритм поиска цикла Флойда: этот метод использует два указателя, один из которых движется медленнее, чем другой, а другой — быстрее. Более быстрый указатель в конечном итоге обгонит более медленный указатель, если в связанном списке есть петля, обнаруживая существование петли.

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

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

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

Подход 1: Подход HashSet

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

Реализовать эту стратегию будет довольно легко.

При переходе по связанному списку мы будем использовать unordered_hashmap и продолжать добавлять к нему узлы.

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

• • Кроме того, мы сохранили два указателя на каждом шаге, головной узел указывая на текущий узел и последний узел указывая на предыдущий узел текущего узла во время итерации.
  • Как наш головной узел теперь указывает на начальный узел цикла и как последний узел указывал на узел, на который указывала голова (т. последний узел петли), наш головной узел в настоящее время указывает на начальный узел цикла.
  • Цикл будет разорван установкой l astNode->следующий == NULL .

Делая это, конечный узел цикла вместо ссылки на начальный узел цикла начинает указывать на NULL.

Средняя временная и пространственная сложность метода хеширования составляет O(n). Читатель всегда должен знать, что реализация встроенной Hashing DataStructure в языке программирования будет определять общую временную сложность в случае коллизии при хешировании.

Программная реализация C++ для вышеуказанного метода (HashSet):

Выход:

Пошаговое объяснение кода приведено ниже:

1. 1. Заголовочный файл bits/stdc++.h>, содержащий все распространенные библиотеки C++, включен в код.
   2. Строится структура под названием «Узел», состоящая из двух элементов: ссылки на следующий узел в списке и целое число, называемое «значение».
   3. С целочисленным значением в качестве входных данных и указателем «следующий», установленным в NULL, функция «newNode» создает новый узел с этим значением.
   4. Функция ' функцияHashMap’ определен, который принимает указатель на головной узел связанного списка в качестве входных данных.
   5. Внутри ' функцияHashMap ‘, создается unordered_map с именем ‘hash_map’, который используется для реализации структуры данных хеш-карты.
   6. Указатель на последний узел списка инициализируется значением NULL.
   7. Цикл while используется для обхода связанного списка, который начинается с головного узла и продолжается до тех пор, пока головной узел не станет NULL.
   8. Указатель lastNode обновляется до текущего узла внутри цикла while, если текущий узел (headNode) еще не присутствует в хэш-карте.
   9. Если текущий узел найден на карте, это означает, что в связанном списке присутствует петля. Чтобы удалить цикл, следующий указатель последний узел установлен на НУЛЕВОЙ и цикл while прерывается.
   10. Головной узел связанного списка используется в качестве входных данных для функции display, которая выводит значение каждого узла в списке от начала до конца.
   11. в основной функция, создающая петлю.
   12. Функция functionHashMap вызывается с указателем headNode в качестве входных данных, что удаляет цикл из списка.
   13. Измененный список отображается с помощью функции «отображение».

Подход 2: Цикл Флойда

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

1. В головном узле связанного списка мы инициализируем два указателя, называемых быстрым и медленным.

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

3. В связанном списке не будет цикла, если быстрый указатель достигнет конца списка (fastPointer == NULL или fastPointer->next == NULL). В противном случае быстрый и медленный указатели в конечном итоге встретятся, что означает, что связанный список имеет петлю.

Программная реализация C++ для описанного выше метода (цикл Флойда):

Выход:

Объяснение:

1. 1. Сначала включаются соответствующие заголовки, такие как «bits/stdc++.h» и «std::cout».
   2. Затем объявляется структура «Node», обозначающая узел в связанном списке. Следующий указатель, который ведет к следующему узлу в списке, включается вместе с целочисленным полем данных в каждый узел.
   3. Затем он определяет две функции «deleteLoop» и «detectAndDeleteLoop». Цикл удаляется из связанного списка с помощью первого метода, а цикл обнаруживается в списке с помощью второй функции, которая затем вызывает первую процедуру для удаления цикла.
   4. В основной функции создается новый связанный список с пятью узлами, а цикл устанавливается путем установки указателя next последнего узла на третий узел.
   5. Затем он вызывает метод «detectAndDeleteLoop», передавая в качестве аргумента головной узел связанного списка. Для выявления циклов эта функция использует подход «медленных и быстрых указателей». Он использует два указателя, которые начинаются вверху списка, slowPTR и fastPTR. В то время как быстрый указатель перемещает два узла одновременно, медленный указатель перемещает только один узел за раз. Быстрый указатель в конечном итоге обгонит медленный указатель, если список содержит цикл, и две точки столкнутся в одном и том же узле.
   6. Функция вызывает функцию «deleteLoop», если находит цикл, предоставляя в качестве входных данных головной узел списка и пересечение медленного и быстрого указателей. Эта процедура устанавливает два указателя, ptr1 и ptr2, на головной узел списка и подсчитывает количество узлов в цикле. После этого он продвигает один указатель на k узлов, где k — общее количество узлов в цикле. Затем, пока они не встретятся в начале цикла, он продвигает обе точки по одному узлу за раз. Затем цикл прерывается установкой следующего указателя узла в конце цикла в NULL.
   7. После удаления цикла он отображает связанный список в качестве последнего шага.

Подход 3: рекурсия

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

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

Список содержит цикл, если узел, который ранее был помечен как посещенный, встречается с функцией; в этом случае функция может вернуть true. Метод может вернуть false, если он достигает конца списка, не проходя через посещенный узел, что указывает на отсутствие цикла.

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

Программная реализация C++ для вышеуказанного метода (рекурсия):

Выход:

Объяснение:

1. 1. Функция обнаружитьLoopLinkedList() в этой программе в качестве входных данных используется заголовок связанного списка.
   2. Рекурсия используется функцией для перебора связанного списка. В базовом случае рекурсия начинается с определения того, является ли текущий узел NULL. Если это так, метод возвращает false, указывая на отсутствие цикла.
   3. Затем проверяется значение свойства «visited» текущего узла, чтобы узнать, посещался ли он ранее. Он возвращает true, если он был посещен, предполагая, что петля была найдена.
   4. Функция помечает текущий узел как посещенный, если он уже был посещен, изменив его свойство «visited» на true.
   5. Затем значение посещаемой переменной проверяется, чтобы увидеть, посещался ли текущий узел ранее. Если она использовалась ранее, цикл должен существовать, и функция возвращает значение true.
   6. Наконец, функция вызывает себя со следующим узлом в списке, передавая головной узел-> следующий как аргумент. Рекурсивно , это выполняется до тех пор, пока не будет найдена петля или не будут посещены все узлы. Означает, что функция устанавливает переменную посещений в значение true, если текущий узел никогда не посещался до рекурсивного вызова самого себя для следующего узла в связанном списке.
   7. Код создает три узла и объединяет их для создания связанного списка в основная функция . Метод обнаружитьLoopLinkedList() затем вызывается на головном узле списка. Программа производит « Цикл вычитается в связанном списке ' если обнаружитьLoopLinkedList() возвращает истину; в противном случае он выводит « В связанном списке цикл не обнаружен “.
   8. Затем код вставляет цикл в связанный список, устанавливая указатель next последнего узла на второй узел. Затем, в зависимости от результата функции, она запускается обнаружитьLoopLinkedList() снова и производит либо “ Цикл вычитается в связанном списке ' или ' В связанном списке цикл не обнаружен ».

Подход 4: использование стека

Циклы в связанном списке можно найти с помощью стека и метода «поиска в глубину» (DFS). Фундаментальная концепция состоит в том, чтобы перебирать связанный список, помещая каждый узел в стек, если он еще не был посещен. Цикл распознается, если узел, который уже находится в стеке, встречается снова.

Вот краткое описание процедуры:

1. 1. Создайте пустой стек и переменную для записи посещенных узлов.
   2. Поместите связанный список в стек, начиная сверху. Отметьте, что голова была посещена.
   3. Поместите следующий узел в списке в стек. Добавьте метку посещения к этому узлу.
   4. Когда вы проходите по списку, помещайте каждый новый узел в стек, чтобы указать, что он был посещен.
   5. Проверьте, находится ли ранее посещенный узел на вершине стека, если он встречается. Если это так, петля найдена, и петля идентифицируется узлами в стеке.
   6. Извлеките узлы из стека и продолжайте обход списка, если цикл не найден.

Реализация программы C++ для вышеуказанного метода (стек)

Выход:

Объяснение:

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

• 1. Библиотека потока ввода/вывода и библиотека стека присутствуют в первой строке.

  2. Стандартное пространство имен включено во вторую строку, что позволяет нам получить доступ к функциям библиотеки потоков ввода/вывода без префикса «std::».

  3. Следующая строка определяет структуру Node, которая состоит из двух элементов: целого числа с именем «данные» и указателя на другой узел с именем «следующий».

  4. Заголовок связанного списка является входными данными для метода detectLoopLinkedList(), который определен в следующей строке. Функция выдает логическое значение, указывающее, была ли найдена петля.

  5. Внутри функции создается стек указателей узлов, называемый «stack», и указатель на узел, называемый «tempNode», который инициализируется значением headNode.

  6. Затем, пока tempNode не является нулевым указателем, мы входим в цикл while.

  (a) Верхний элемент стека должен соответствовать текущему узлу, чтобы мы могли определить, что он не пуст. Мы возвращаем true, если это так, потому что была найдена петля.

  (b) Если вышеупомянутое условие ложно, указатель текущего узла помещается в стек, а tempNode устанавливается на следующий узел в связанном списке.

  7. Мы возвращаем false после цикла while, потому что цикла не наблюдалось.

  8. Мы создаем три объекта Node и инициализируем их в функции main(). Поскольку в первом примере нет цикла, мы правильно устанавливаем указатели «следующие» для каждого узла.

Заключение:

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