Условия задачи: есть связный список, и нужно понять, есть ли в нем цикл. Цикл — это когда у нас последний элемент списка ссылается не на null, а на какой-то из элементов этого самого списка, короче, смотрите картинку.
Начну с того, что я вообще не ебу, где такое можно применять. Я понимаю алгоритм поиска цикла в графе, который применяется повсеместно, но в связном списке... Цикл в связном списке — это баг реализации, но да ладно.
Сложность тут в том, что его не решишь обычными способами вроде "запомнить все элементы в set и потом проверять по нему". В этом списке нет индексов, элементы могут повторяться, и мы заранее не знаем, где его конец.
Поэтому поступаем изящнее – два указателя. Один нормальный, который идет по элементам, второй в жопу ужаленный, который скачет через элемент. Если запустить два этих указателя, то у нас может быть два кейса:
👉 быстрый указатель упрется в null – цикла нет
👉 они встретятся на каком-то из элементов – цикл есть
Это собственно все... Код решения на python:
class ListNode:
def __init__(self, x, next):
self.val = x
self.next = next
def detect_cycle(head: ListNode) -> bool:
fast = slow = head
circle_detected = False
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
circle_detected = True
break
return circle_detected
В некоторых случаях могут попросить вернуть ссылку на начало цикла, в этом случае вам нужно будет подвигать ссылку head до нужного места.