На видео более подробное объяснение каждого решения
Постановка задачи
Ссылка на задачу: 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
, указатели встретились на узле со значением 5, что указывает на наличие цикла.