Обнаружение цикла - это алгоритмическая проблема поиска цикла в последовательности повторяющихся значений функции, например, классическая проблема обнаружения цикла со связным списком. Есть разные решения. В следующем примере Leetcode я объясню истинные решения.
Учитывая head
, заголовок связанного списка, определите, есть ли в связанном списке цикл.
В связанном списке есть цикл, если в списке есть какой-то узел, к которому можно снова добраться, непрерывно следуя за указателем next
. Внутри pos
используется для обозначения индекса узла, к которому подключен указатель next
хвоста. Обратите внимание, что pos
не передается в качестве параметра.
Вернуть true
, если в связанном списке есть цикл. В противном случае верните false
.
Example 1: Input: head = [3,2,0,-4], pos = 1 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2: Input: head = [1,2], pos = 0 Output: true Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3: Input: head = [1], pos = -1 Output: false Explanation: There is no cycle in the linked list.
Ограничения:
- Количество узлов в списке находится в диапазоне
[0, 104]
. -105 <= Node.val <= 105
pos
- это-1
или действительный индекс в связанном списке.
Решение 1. Хеширование
- Просмотрите указанный связанный список и сохраните узлы в объекте Set (), чтобы избежать дублирования значений
- Если происходит дублирование, связанный список представляет собой цикл, функция возвращает
true
- После обхода, если дублирующийся узел не найден, функция возвращает
false
Временная сложность: O (n). Требуется только один обход связанного списка.
Сложность пространства: O (n). n - это пространство, необходимое для хранения узлов в Set ().
Решение 2. Алгоритм Флойда "черепаха и заяц"
- Пройдите по заданному списку с двумя указателями
- Медленный указатель перемещается на один, быстрый указатель на два
- Если два указателя встречаются, возвращает
true
, если нет -false
Временная сложность: O (n). Требуется только один обход связанного списка.
Сложность пространства: O (1). Место не требуется, оно постоянно.
Ресурсы: