Обнаружение циклов алгоритмом Флойда
Обнаруживайте циклы с помощью медленного и быстрого указателей, находите точку входа в цикл и математически доказывайте корректность алгоритма
«Обнаружение циклов алгоритмом Флойда» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 3 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.
Что такое цикл в связном списке
Цикл в связном списке возникает, когда указатель next узла указывает на ранее посещенный узел, создавая бесконечный цикл. Обход такого списка с помощью цикла while head продолжался бы бесконечно. Обнаружение циклов — классическая задача на собеседованиях и основа более сложных алгоритмов работы с указателями.
Наивный подход сохраняет каждый посещенный узел во множестве и проверяет его наличие — время O(n), память O(n). Алгоритм Флойда решает ту же задачу за время O(n) и с памятью O(1), чего и ожидают интервьюеры.
Алгоритм Флойда с медленным и быстрым указателями
Для обнаружения циклов алгоритм Флойда (метод «черепахи и зайца») использует два указателя: slow продвигается на один шаг за раз, а fast — на два. Если цикла нет, fast первым достигает None. Если цикл есть, fast в конце концов обгоняет slow внутри цикла, и они встречаются в одном узле. Эта встреча доказывает наличие цикла.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# Build: 3 -> 2 -> 0 -> -4 -> (back to 2)
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1] # cycle: -4 -> 2
print(hasCycle(nodes[0])) # TrueПочему медленный и быстрый указатели всегда встречаются
Неформально: после входа обоих указателей в цикл расстояние между ними изменяется на 1 за шаг (fast проходит 2 шага, slow — 1, поэтому разрыв сокращается на 1 за каждый раунд). В конце концов разрыв становится равен 0 — указатели оказываются в одном узле. Формально, если длина цикла равна C, максимальный разрыв внутри цикла равен C-1, а разрыв сокращается на 1 за шаг, поэтому указатели встретятся не позднее чем через C шагов после входа обоих в цикл.
Общее число шагов до встречи: не более O(n + C) = O(n), поскольку C <= n.
# Visualise convergence: simulate gap in cycle
cycle_length = 5
for start_gap in range(1, cycle_length + 1):
gap = start_gap
steps = 0
while gap != 0:
gap = (gap - 1) % cycle_length
steps += 1
print(f'Start gap {start_gap}: meet after {steps} step(s)')Поиск точки входа в цикл
После обнаружения цикла алгоритм Флойда также может найти входной узел (узел, с которого начинается цикл). После встречи slow и fast внутри цикла верните один указатель в голову, а другой оставьте в точке встречи. Затем продвигайте оба указателя на один шаг за раз. Они встретятся ровно во входном узле цикла. Это работает, потому что расстояние от головы до точки входа равно расстоянию от точки встречи до точки входа по модулю длины цикла.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
slow = fast = head
# Phase 1: detect meeting point
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None # no cycle
# Phase 2: find entry
pointer = head
while pointer is not slow:
pointer = pointer.next
slow = slow.next
return pointer # cycle entry node
nodes = [ListNode(v) for v in [3, 2, 0, -4]]
for i in range(3):
nodes[i].next = nodes[i+1]
nodes[3].next = nodes[1] # entry is nodes[1] (val=2)
entry = detectCycle(nodes[0])
print(entry.val) # 2Математическое доказательство точки входа
Пусть F = расстояние от головы до точки входа в цикл, C = длина цикла, а a = расстояние от точки входа до точки встречи внутри цикла. В момент встречи slow прошел F + a шагов, а fast — F + a + n*C шагов (на n полных кругов впереди). Поскольку fast = 2 * slow: 2(F+a) = F+a+nC → F = nC - a. Это означает, что расстояние от головы до точки входа равно расстоянию от точки встречи до точки входа по модулю C. Если вернуть один указатель в голову и продвигать оба на 1 шаг, они сойдутся во входном узле.
# Verify with our example: F=1 (head to node 2), C=3 (cycle: 2->0->-4->2), a=?
# Meeting inside cycle after F+a slow steps
# Let us measure a by counting from entry to meeting point
# In practice the code handles this automatically
F = 1 # head(3) to entry(2)
C = 3 # cycle length 2->0->-4
# n=1: F = 1*C - a => a = C - F = 3 - 1 = 2
a = C - F
print(f'F={F}, C={C}, a={a}')
print(f'After meeting, {F} more steps reach entry: {F == C - a or F % C == (C - a) % C}')Измерение длины цикла
Получив точку встречи внутри цикла (первую фазу алгоритма Флойда), вы можете измерить длину цикла: оставьте один указатель неподвижным, а другой продвигайте, пока они снова не встретятся. Число выполненных шагов равно длине цикла. Это полезно в задачах, где длину цикла требуется найти явно.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def cycle_length(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast: # found meeting point
length = 1
fast = fast.next
while fast is not slow:
fast = fast.next
length += 1
return length
return 0 # no cycle
nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2] # cycle: 3->4->5->3, length=3
print(cycle_length(nodes[0])) # 3Счастливое число (обнаружение цикла без списка)
Алгоритм Флойда применим не только к связным спискам. В задаче LeetCode 202 «Happy Number» требуется определить, достигает ли число 1, если многократно заменять n суммой квадратов его цифр. Если последовательность входит в цикл, не содержащий 1, она будет выполняться бесконечно. Это можно представить как обход виртуального связного списка, где значение 'next' каждого узла — это следующее вычисленное значение, а затем применить алгоритм Флойда для обнаружения цикла.
def isHappy(n):
def next_val(x):
total = 0
while x:
x, d = divmod(x, 10)
total += d * d
return total
slow, fast = n, next_val(n)
while fast != 1 and slow != fast:
slow = next_val(slow)
fast = next_val(next_val(fast))
return fast == 1
print(isHappy(19)) # True (1->81+1=82->68->100->1)
print(isHappy(2)) # False (enters cycle)Наивное обнаружение с помощью множества и алгоритм Флойда
Подход с множеством сохраняет каждый посещенный узел во множестве и проверяет его наличие перед посещением. Он использует время O(n) и память O(n). Алгоритм Флойда также работает за время O(n), но использует только память O(1) — дополнительная структура данных не нужна. В средах с ограниченной памятью (встроенные системы, ядра операционных систем) гарантия памяти O(1) имеет значение. Иногда интервьюеры после решения с множеством отдельно просят обеспечить память O(1).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Naive O(n) space approach
def hasCycle_set(head):
seen = set()
while head:
if id(head) in seen:
return True
seen.add(id(head))
head = head.next
return False
# Floyd's O(1) space approach
def hasCycle_floyd(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
print('Both implementations give the same result')Граничные случаи при обнаружении циклов
Нужно обработать три граничных случая. Во-первых, пустой список: head is None — условие цикла Флойда fast and fast.next немедленно становится ложным, и возвращается False. Во-вторых, один узел без цикла: fast.next равен None, цикл завершается, возвращается False. В-третьих, один узел с циклом: next узла указывает на него самого — slow и fast начинают с head; после одного шага fast перемещается в head.next.next = head, а slow оказывается в head.next = head. Поэтому fast == slow уже на первой итерации.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
return True
return False
# Edge cases
print(hasCycle(None)) # False: empty
node = ListNode(1)
print(hasCycle(node)) # False: single, no cycle
node.next = node
print(hasCycle(node)) # True: single node cycleЦикл в связном списке II: LeetCode 142
В задаче LeetCode 142 «Linked List Cycle II» требуется найти узел, с которого начинается цикл (или вернуть None, если цикла нет). Это непосредственное применение двухфазного алгоритма Флойда. Интервьюеры задают эту задачу как продолжение базовой задачи на обнаружение цикла. Полное решение: первая фаза находит точку встречи внутри цикла; во второй фазе один указатель возвращается в голову, и оба указателя продвигаются вперед, пока не встретятся — эта точка встречи и есть вход в цикл.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def detectCycle(head):
slow = fast = head
# Phase 1
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow is fast:
break
else:
return None
# Phase 2
ptr = head
while ptr is not slow:
ptr = ptr.next
slow = slow.next
return ptr
nodes = [ListNode(v) for v in [1, 2, 3, 4, 5]]
for i in range(4):
nodes[i].next = nodes[i+1]
nodes[4].next = nodes[2] # cycle entry: node with val=3
entry = detectCycle(nodes[0])
print(entry.val) # 3Почему алгоритм Флойда лучше подхода с множеством
Хотя оба подхода имеют временную сложность O(n), на практике их постоянные множители различаются. Подход с множеством должен хешировать указатель каждого узла (вычислять хеш, обращаться к хеш-таблице и сохранять указатель), тогда как алгоритм Флойда выполняет только разыменование указателей — на каждом шаге это гораздо дешевле. Что еще важнее, гарантия памяти O(1) позволяет алгоритму Флойда работать со списками произвольной длины без риска исчерпать память.
Если на собеседовании заранее упомянуть это преимущество по памяти, вы покажете глубокое понимание компромиссов алгоритмов, выходящее за рамки самой записи Big-O.
Быстрая проверка
Проверьте свое понимание концепций «Структуры данных и алгоритмы — подготовка к техническому собеседованию» из этого урока.
Итоги урока
В этом уроке вы узнали, что алгоритм Флойда с медленным и быстрым указателями обнаруживает циклы за время O(n) и с дополнительной памятью O(1), вторая фаза (вернуть один указатель в голову и продвигать оба на 1) находит точный входной узел цикла, а тот же метод применим не только к связным спискам, но и к любой неявной последовательности, в которой 'next' является функцией. Далее мы рассмотрим слияние отсортированных списков, разделение списков по середине и поиск узла с номером n от конца.
Часто задаваемые вопросы
Урок «Обнаружение циклов алгоритмом Флойда» бесплатный?
Да — полный текст урока «Обнаружение циклов алгоритмом Флойда» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Обнаружение циклов алгоритмом Флойда»?
Обнаруживайте циклы с помощью медленного и быстрого указателей, находите точку входа в цикл и математически доказывайте корректность алгоритма Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Coding Interview Prep?
Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 3 из 4.
Сколько времени занимает урок «Обнаружение циклов алгоритмом Флойда»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Coding Interview Prep?
Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Класс узла и построение списка
- Разворот связного списка
- Обнаружение циклов алгоритмом Флойда
- Слияние, разделение и поиск с конца