Цикл в списке: алгоритм Флойда

Два указателя с разной скоростью обнаружат цикл, не занимая лишней памяти.

Алгоритм Флойда («черепаха и заяц») — поиск цикла двумя указателями, движущимися с разной скоростью.

Зачем это нужно

Если в списке есть цикл (хвост ссылается на предыдущий узел), наивный обход зациклится навсегда. Можно хранить все посещённые узлы в множестве — но это O(n) памяти. Алгоритм Флойда обходится O(1) памяти.

Идея «черепахи и зайца»

Медленный указатель (черепаха) движется на 1 узел за шаг, быстрый (заяц) — на 2. Если цикла нет, заяц добежит до конца. Если цикл есть, заяц рано или поздно «догонит» черепаху внутри цикла — указатели совпадут.

class Node:
    def __init__(self, val):
        self.val = val
        self.next = None

def has_cycle(head):
    slow = head
    fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

# список без цикла: 1 -> 2 -> 3
a, b, c = Node(1), Node(2), Node(3)
a.next, b.next = b, c
print(has_cycle(a))

# добавим цикл: 3 -> 1
c.next = a
print(has_cycle(a))

Вывод:

False
True

Как работает под капотом

Почему быстрый обязательно догонит медленного? Войдя в цикл, оба бегают по кольцу. На каждом шаге заяц сокращает расстояние до черепахи ровно на 1 (он движется на 2, она на 1, относительная скорость 1). Расстояние конечно (длина цикла), поэтому за конечное число шагов оно станет нулём — указатели совпадут. Условие fast and fast.next защищает от обращения к None.next на списке без цикла. Время O(n), память O(1).

Частые ошибки

• Сравнивать slow.val == fast.val вместо slow is fast — значения могут совпадать у разных узлов.
• Проверять только fast, забыв fast.next — упадёте на None.next.
• Стартовать указатели с разных узлов — классический вариант стартует с одного head.

Итог

• Алгоритм Флойда находит цикл за O(n) время и O(1) память.
• Заяц движется вдвое быстрее и догоняет черепаху внутри цикла.
• Сравнивайте узлы по идентичности (is), а не по значению.