Быстрый и медленный указатели: цикл и середина списка без лишней памяти

Короткий ответ. Быстрый и медленный указатели идут по одному списку с разной скоростью. Медленный делает шаг, быстрый два. Если они встретились, в списке есть цикл. Тот же приём находит середину списка за один проход без лишней памяти. Ниже сигналы в условии, код на Python и доказательство для начала цикла.

Что такое быстрый и медленный указатели?

Берём две ссылки на узлы связного списка. Обе стартуют с головы. На каждом шаге медленный сдвигается на один узел, быстрый на два.

Если цикла нет, быстрый первым дойдёт до конца. Если цикл есть, быстрый догонит медленного. Они окажутся на одном узле.

Приём ещё называют алгоритмом Флойда или «черепаха и заяц». Ему нужна O(1) памяти. В этом его смысл.

По каким словам в задаче узнать приём?

• «Найти цикл в списке» без дополнительной памяти.
• «Найти середину списка» за один проход.
• «Счастливое число» и любая последовательность, которая может зациклиться.
• «Найти повторяющееся число» в массиве со значениями от 1 до n.

Общий признак: по данным можно идти только вперёд. Индекса для прыжка нет. Хеш-множество тоже решает, но стоит O(n) памяти. На собеседовании просят вариант за O(1).

В реальных системах приём ловит зацикленные ссылки. Например, цепочку редиректов, где страница в итоге ведёт на саму себя. Или список задач, где зависимость замкнулась.

Как быстрый и медленный указатели находят середину?

Медленный шагает по одному, быстрый по два. Когда быстрый упёрся в конец, медленный стоит на середине.

При чётной длине середин две. Код ниже возвращает вторую. Чтобы получить первую, остановите быстрый на один узел раньше.

Как это выглядит на примере?

Список 1, 2, 3, 4, 5, и узел 5 ссылается обратно на 3. Шаг 1: медленный на 2, быстрый на 3. Шаг 2: медленный на 3, быстрый на 5. Шаг 3: медленный на 4, быстрый на 4. Встреча, цикл есть.

Теперь ищем начало цикла. Медленный возвращается на 1, быстрый остаётся на 4. Оба идут по одному узлу. Шаг: 2 и 5. Шаг: 3 и 3. Встретились на узле 3, это и есть вход в цикл.

Как написать приём на Python?

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

def middle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow

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

def cycle_start(head):
    slow = fast = head
    while fast and fast.next:
        slow, fast = slow.next, fast.next.next
        if slow is fast:
            break
    else:
        return None
    slow = head
    while slow is not fast:
        slow, fast = slow.next, fast.next
    return slow

Почему поиск начала цикла работает?

Пусть от головы до входа в цикл a узлов. Длина цикла c. В момент встречи медленный прошёл a + k шагов. Быстрый прошёл вдвое больше.

Разница между ними это целое число кругов. Значит a + k делится на c. Ставим один указатель на голову. Ведём оба по одному шагу. Через a шагов первый дойдёт до входа. Второй пройдёт ещё a шагов внутри цикла и тоже окажется на входе.

Чем приём лучше хеш-множества?

Способ	Время	Память	Находит вход в цикл
Множество посещённых узлов	O(n)	O(n)	Да, первый повтор
Быстрый и медленный указатели	O(n)	O(1)	Да, вторая фаза
Пометки прямо в узлах	O(n)	O(1)	Да, но портит входные данные

Множество короче в коде. Два указателя берут, когда просят O(1) памяти.

Как решить Find the Duplicate Number этим приёмом?

Массив из n + 1 чисел со значениями от 1 до n. Одно число повторяется. Менять массив и тратить память нельзя.

Считаем значение указателем: индекс i ведёт в индекс nums[i]. Два индекса ведут в одно место, значит в таком обходе есть цикл. Повтор это вход в цикл. Запускаем cycle_start на этом обходе.

На каких ошибках ломается решение?

• Проверяют только fast и не проверяют fast.next. На нечётной длине это падение.
• Сравнивают значения через ==, а не узлы через is. Два узла могут хранить одно число.
• Стартуют быстрый с head.next. Доказательство выше требует общий старт.
• Забывают пустой список. Возвращайте ответ сразу, если head равен None.

Как объяснить приём на собеседовании?

Сначала назовите ограничение: O(1) памяти. Потом скорости: один и два. Затем факт: в цикле быстрый догоняет медленного за один круг. И пишите цикл.

Спросят про вход в цикл, скажите «вторая фаза, один указатель на голову». Приведите довод про a + k в двух фразах. Этого хватит.

Отработать узнавание приёма можно на странице быстрый и медленный указатели. Соседний приём разобран на странице разворот связного списка.

Вопросы и ответы

Почему скорость два, а не три?

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

Как найти длину цикла?

После встречи оставьте один указатель на месте. Второй ведите по одному узлу и считайте шаги. Когда он вернётся, счётчик покажет длину цикла.

Работает ли приём на массивах?

Да, когда значение можно читать как следующий индекс. Find the Duplicate Number ровно такой случай.

Можно ли так найти k-й узел с конца?

Это другой приём из той же семьи. Оба указателя идут со скоростью один, между ними зазор в k узлов.