На видео более подробное объяснение каждого решения
Постановка задачи
Ссылка на задачу: https://leetcode.com/problems/linked-list-cycle
Дан head
, являющийся головой связного списка, необходимо определить, есть ли в списке цикл.
Цикл в связном списке существует, если есть такой узел, до которого можно снова добраться, непрерывно следуя указателям next
. Внутренне используется переменная pos
, чтобы указать индекс узла, к которому присоединен указатель next
последнего узла (хвоста). Обратите внимание, что pos
не передается как параметр.
Верните true
, если в связном списке есть цикл. В противном случае верните false
.
1. Решение с использованием set
Подход
Для решения задачи о проверке наличия цикла в связном списке можно использовать структуру данных set
. Мы будем проходить по всем узлам списка и сохранять каждый посещенный узел в set
. Если мы встречаем узел, который уже есть в этом множестве, значит, в списке есть цикл. Если мы дошли до конца списка, не встретив повторяющегося узла, значит, цикла нет.
Алгоритм
Инициализируем пустое множество
seen
, чтобы хранить посещенные узлы.Начинаем с головы списка
head
.-
Пока текущий узел не равен
None
:• Если текущий узел уже есть в
seen
, возвращаемtrue
— в списке есть цикл.• Если текущего узла нет в
seen
, добавляем его в множество.• Переходим к следующему узлу.
Если дошли до конца списка (указатель
next
на последнем узле равенNone
), возвращаемfalse
— цикла нет.
Код решения
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
Сложность алгоритма
По времени: O(n), где n — количество элементов в списке, так как мы проходим по каждому элементу один раз.
По памяти: O(n), так как мы сохраняем все уникальные элементы списка в множество.
Визуализация
Пример 1 (Список без цикла)
Исходный список:
1 -> 2 -> 3 -> 4 -> 5 -> None
Текущий узел: 1, seen =
{1}
Текущий узел: 2, seen =
{1, 2}
Текущий узел: 3, seen =
{1, 2, 3}
Текущий узел: 4, seen =
{1, 2, 3, 4}
Текущий узел: 5, seen =
{1, 2, 3, 4, 5}
Результат: False
, так как узлы не повторяются и конец списка был достигнут.
Пример 2 (Список с циклом)
Исходный список:
1 -> 2 -> 3 -> 4 -> 5
^ |
|---------|
Текущий узел: 1, seen =
{1}
Текущий узел: 2, seen =
{1, 2}
Текущий узел: 3, seen =
{1, 2, 3}
Текущий узел: 4, seen =
{1, 2, 3, 4}
Текущий узел: 5, seen =
{1, 2, 3, 4, 5}
Текущий узел: 3 (уже в
seen
)
Результат: True
, так как узел 3 повторяется, следовательно, есть цикл.
2. Решение с использованием двух указателей
Подход
В этом решении используется техника двух указателей — медленного (slow
) и быстрого (fast
). Они оба начинаются с головы списка, но slow
двигается на один узел за раз, а fast
— на два узла. Если в списке есть цикл, то в какой-то момент slow
и fast
встретятся в одном узле. Если fast
достигнет конца списка (т.е. fast
или fast.next
станет None
), значит, цикла нет.
Алгоритм
Инициализируем два указателя:
slow
иfast
, оба начинаются с головы спискаhead
.-
Запускаем цикл, пока
fast
иfast.next
не равныNone
:• Двигаем
slow
на один шаг вперед.• Двигаем
fast
на два шага вперед.• Если
slow
иfast
встретились, возвращаемTrue
— в списке есть цикл. Если цикл завершился без встречи указателей, возвращаем
False
— цикла нет.
Код решения
class Solution:
def hasCycle(self, head: Optional[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
Сложность алгоритма
По времени: O(n), где n — количество элементов в списке, так как указатели проходят по каждому элементу максимум один раз.
По памяти: O(1), так как мы используем только два указателя для обхода списка и не занимаем дополнительную память.
Визуализация
Пример 1 (Список без цикла)
Исходный список:
1 -> 2 -> 3 -> 4 -> 5 -> None
Инициализация:
1 -> 2 -> 3 -> 4 -> 5 -> None
slow
fast
Шаг 1:
1 -> 2 -> 3 -> 4 -> 5 -> None
slow
fast
Шаг 2:
1 -> 2 -> 3 -> 4 -> 5 -> None
slow
fast
Шаг 3:
1 -> 2 -> 3 -> 4 -> 5 -> None
slow
fast (достиг конца)
Результат: False
, так как быстрый указатель достиг конца списка и указатели не встретились.
Пример 2 (Список с циклом)
Исходный список:
1 -> 2 -> 3 -> 4 -> 5
^ |
|---------|
Инициализация:
1 -> 2 -> 3 -> 4 -> 5
slow
fast
Шаг 1:
1 -> 2 -> 3 -> 4 -> 5
slow
fast
Шаг 2:
1 -> 2 -> 3 -> 4 -> 5
slow
fast
Шаг 3:
1 -> 2 -> 3 -> 4 -> 5
slow
fast (по циклу вернулся на 3)
Шаг 4:
1 -> 2 -> 3 -> 4 -> 5
slow
fast (встретились на 5)
Результат: True
, указатели встретились на узле со значением 3, что указывает на наличие цикла.
wataru
Не правда. "Быстрый" указатель может по циклу сделать очень и очень много полных оборотов.
Ну и по статье - разбор баянистых элементарных задачек надо делать не так. Люди, которые их уже знают, от вашей статьи не получили ничего. Люди, которые их не умеют решать, от вашей статьи тоже не получили ничего, потому что им ничего не понятно. Максимум, что они тут могут сделать - это выучить код наизусть. Сомнительной полезности действие.
Вам надо не только приводить код решения (причем два раза: первый раз текстом, второй раз кодом), а объяснять, почему и как оно работает.