Обнаружение цикла связанного списка. (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)

Оригинал

Обнаружение цикла связанного списка. (LeetCode)

Описание задачи

Пример 1:

Пример 2:

Пример 3:

Ограничения:

Решение

Подход 1: использование набора

Подход 2: быстрые и медленные указатели

Recent Post

Мета-обучение: обучение ИИ учиться учиться

Эти алгоритмы предназначены для улучшения состояния человека: они потерпели неудачу

Используйте бесконечность, а не в петлях Python

Квантовое машинное обучение: когда Шредердинг встречает ученых данных

Группа студентов революционизирует то, как вы узнаете, что смотреть, читать и слушать

Categories