Fast and Slow Pointers

Связный список может замыкаться сам на себя, и тогда обычный обход не закончится никогда. Очевидное решение — складывать посещённые узлы в множество и проверять каждый следующий: работает, но стоит $O(n)$ памяти. На списке из миллионов узлов или на последовательности состояний, которую нельзя сохранить целиком, это неприемлемо.

Та же проблема шире, чем списки: повтор состояния в детерминированной последовательности — это цикл, и искать его перебором с запоминанием так же дорого.

Память при этом — два указателя, то есть константа. Ничего не запоминается вообще: факт цикла выводится из встречи, а не из журнала посещений.

1 -> 2 -> 3 -> 4
          ^    |
          +----+

шаг 0:   S = 1    F = 1
шаг 1:   S = 2    F = 3
шаг 2:   S = 3    F = 3   встретились -- цикл есть

Если бы цикла не было, быстрый просто упёрся бы в конец списка: условие fast and fast.next перестало бы выполняться, и цикл завершился бы без встречи.

slow = fast = head

while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
    if slow is fast:
        break
else:
    return None                 # цикла нет

slow = head                     # второй этап: ищем вход в цикл
while slow is not fast:
    slow = slow.next
    fast = fast.next
return slow

• Время — $O(\mu +\lambda )$, то есть линейное по числу узлов.
• Память — $O(1)$: два указателя и ничего больше.
• Предусловие — переход из узла детерминирован: у каждого состояния ровно один следующий.

Как только оба указателя оказались внутри цикла, рассмотрим расстояние от быстрого до медленного по направлению движения. За один шаг медленный продвигается на 1, быстрый на 2, значит расстояние сокращается ровно на 1 — и, будучи целым неотрицательным, рано или поздно обнуляется. Перепрыгнуть друг друга они не могут именно потому, что разница скоростей равна единице.

Второй этап опирается на арифметику: к моменту встречи медленный прошёл $\mu +k$ шагов, быстрый — вдвое больше, а разница между ними кратна длине цикла. Отсюда следует, что расстояние от головы до входа в цикл и расстояние от точки встречи до входа сравнимы по модулю $\lambda$ — поэтому два указателя, идущие по шагу из головы и из точки встречи, сходятся именно во входе.

Параметр здесь ровно один — соотношение скоростей. Классическое 1 и 2 удобно тем, что встреча гарантирована и доказывается в одну строку; при скоростях 1 и 3 указатели могут перепрыгивать друг друга, и условие встречи усложняется.

• Порядок проверок. while fast and fast.next — иначе обращение к fast.next.next падает на списке чётной длины.
• Какая середина. При чётном числе узлов «середин» две; какая нужна, определяет начальное положение указателей.
• Сравнение узлов, а не значений. Проверять нужно тождество узлов (is), иначе два одинаковых значения выглядят как встреча.
• Изменение списка во время обхода. Развернуть половину списка для проверки палиндрома удобно, но список остаётся изменённым — если это API, его надо восстановить.
• Недетерминированный переход. Если у состояния несколько следующих, это уже граф, и цикл ищется обходом в глубину.

1. Почему указатели со скоростями 1 и 2 обязаны встретиться, а не перепрыгнуть друг друга?
2. Список из одного узла, ссылающегося на себя: отработает ли ваш код?
3. Найдите середину списка за один проход — и скажите, какую из двух середин вернёт ваш код при чётной длине.
4. Почему поиск входа в цикл начинается именно из головы списка?
5. Массив [1, 3, 4, 2, 2]: как здесь возникает цикл и почему дубликат — это вход в него?