Обнаружение цикла связанного списка. (LeetCode)
16 ноября 2022 г.Описание задачи
Данный заголовок, заголовок связанного списка, определяет, есть ли в связанном списке цикл. В связанном списке есть цикл, если в списке есть какой-то узел, к которому можно снова добраться, непрерывно следуя за следующим указателем. Внутри pos используется для обозначения индекса узла, к которому подключен следующий указатель tail. Обратите внимание, что pos не передается в качестве параметра.
Возвращает true, если в связанном списке есть цикл. В противном случае вернуть false.
Пример 1:
Ввод: голова = [3,2,0,-4], позиция = 1 Вывод: правда Объяснение: в связанном списке есть цикл, хвост которого соединяется с 1-м узлом (с индексом 0).
Пример 2:
Ввод: голова = [1,2], позиция = 0 Вывод: правда Объяснение: В связанном списке есть цикл, хвост которого соединяется с 0-м узлом.
Пример 3:
Ввод: голова = [1], позиция = -1 Вывод: ложь Объяснение: в связанном списке нет цикла.
Ограничения:
Количество узлов в списке находится в диапазоне [0, 104]. -105 <= Node.val <= 105 pos равно -1 или допустимому индексу в связанном списке.
Решение
Подход 1: использование набора
Мы можем использовать набор для хранения уже посещенных узлов. Затем мы можем просмотреть связанный список и проверить, находится ли текущий узел в наборе. Если это так, мы возвращаем True. Если мы достигаем конца связанного списка, мы возвращаем False.
def has_cycle(head: ListNode) -> bool:
visited = set()
current = head
while current:
if current in visited:
return True
visited.add(current)
current = current.next
return False
https://youtu.be/RpjyyMgp9b8?embedable=true
https://youtu.be/TC-yafgcK9A?embedable=true
Временная сложность - O(n) Пространственная сложность - O(n)
Подход 2: быстрые и медленные указатели
Для решения этой проблемы мы можем использовать два указателя. Быстрый указатель перемещается на два шага за раз, а медленный указатель перемещается один шаг за раз. Если в связанном списке нет цикла, быстрый указатель достигнет конца связанного списка. первый. Если есть цикл, быстрый указатель в конечном итоге встретится с медленным указателем.
def has_cycle(head: ListNode) -> bool:
slow = head
fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
https://youtu.be/mqx5f1t3kC0?embedable=true
https://youtu.be/cxBYucu6j0g?embedable=true
Временная сложность - O(n) Пространственная сложность - O(1)
Оригинал