Быстрый и медленный указатель: алгоритм Флойда, середина списка и Happy Number

Паттерн быстрого и медленного указателя: почему они встречаются в цикле, как найти середину списка и начало цикла, Happy Number и Find the Duplicate Number. Код на Python.

15 мин чтенияалгоритмы · связные списки · два указателя · python

Коротко

ПараметрЗначение
ВремяO(n)
ПамятьO(1) — вместо множества посещённых
Когда применятьпоследовательность, где каждый элемент однозначно задаёт следующий: связный список, функция x → f(x), массив-«указатель»
Главная идеяодин указатель шагает на 1, другой на 2; в цикле быстрый догоняет медленного, без цикла — первым упирается в конец

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

Идея: два бегуна на одной дорожке

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

В коде это выглядит так:

slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next

Вся магия — в том, что мы проверяем внутри цикла и после него:

  • slow is fast внутри цикла — значит, есть цикл;
  • цикл while закончился сам — цикла нет, а slow стоит ровно на середине;
  • после встречи переставили один указатель в начало и пошли с одинаковой скоростью — встретятся в начале цикла.

Ниже разбираем каждый вариант. Базовую задачу «есть ли цикл в списке» со всеми альтернативами (множество, модификация списка) мы подробно разбирали в статье Обнаружение цикла в связном списке — здесь сосредоточимся на самом паттерне и на задачах, где его не сразу узнаёшь.

Почему быстрый обязательно догонит медленного

Это главный вопрос, который задают на собеседовании после того, как вы написали код.

Пусть оба указателя уже внутри цикла длины LL. Расстояние от fast до slow по ходу движения — dd, где 0<d<L0 < d < L. За один шаг slow уходит вперёд на 1, а fast — на 2. Значит, расстояние между ними уменьшается ровно на 1 за каждый шаг:

d→d−1→d−2→⋯→0d \to d - 1 \to d - 2 \to \dots \to 0

Расстояние убывает по единице, поэтому «перепрыгнуть» через slow быстрый указатель не может. Встреча случится не позже чем через LL шагов после того, как slow вошёл в цикл.

Отсюда же оценка времени: до входа в цикл slow проходит aa шагов (длина «хвоста»), внутри — меньше LL. Итого O(a+L)=O(n)O(a + L) = O(n).

А если fast шагает на 3? Тогда расстояние уменьшается на 2 за шаг, и при нечётном dd и чётном LL указатели могут кружить, не встречаясь в одном узле. Скорости 1 и 2 — не традиция, а самый простой вариант, где встреча гарантирована.

Середина списка

Задача LeetCode 876 «Middle of the Linked List»: вернуть средний узел, а при чётной длине — второй из двух средних.

Наивный способ — пройти список, посчитать длину nn, затем пройти ещё n/2n / 2 шагов. Это тоже O(n)O(n), но два прохода. Быстрый и медленный указатели делают то же самое за один: когда fast дошёл до конца, slow прошёл ровно половину пути.

class ListNode: def __init__(self, val=0, next=None): self.val = val self.next = next def build(values): dummy = ListNode() tail = dummy for v in values: tail.next = ListNode(v) tail = tail.next return dummy.next def middle_node(head): """Для чётной длины возвращает второй из двух средних.""" slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next return slow print(middle_node(build([1, 2, 3, 4, 5])).val) # 3 print(middle_node(build([1, 2, 3, 4, 5, 6])).val) # 4

Первая или вторая середина

В половине задач нужна не вторая, а первая середина: например, чтобы разрезать список на две половины и у левой был последний узел. Меняется только условие цикла:

def middle_node_first(head): """Для чётной длины возвращает первый из двух средних.""" slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next return slow print(middle_node_first(build([1, 2, 3, 4, 5, 6])).val) # 3

Другой распространённый вариант — стартовать с fast = head.next. Эффект тот же: slow остановится на первой середине.

СтартУсловиеСписок 1..6Список 1..5
slow = fast = headfast and fast.next4 (вторая)3
slow = fast = headfast.next and fast.next.next3 (первая)3
slow = head, fast = head.nextfast and fast.next3 (первая)3

Не пытайтесь запомнить таблицу — проще за 10 секунд прогнать в голове список из двух элементов. Это лучший тест на off-by-one в задачах с серединой.

Начало цикла

LeetCode 142 «Linked List Cycle II»: если цикл есть, вернуть узел, с которого он начинается.

Алгоритм Флойда делает это в две фазы:

  1. Быстрый и медленный указатели идут до встречи.
  2. Один указатель переставляем в head, и оба шагают по одному. Узел, где они снова встретятся, — начало цикла.
def detect_cycle(head): 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 # 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> снова 3 nodes = [ListNode(i) for i in range(1, 7)] for a, b in zip(nodes, nodes[1:]): a.next = b nodes[-1].next = nodes[2] print(detect_cycle(nodes[0]).val) # 3 print(detect_cycle(build([1, 2, 3]))) # None

Конструкция while ... else в Python выполняет else, только если цикл завершился без break, — как раз случай «быстрый дошёл до конца».

Почему вторая фаза работает

Обозначим: aa — длина хвоста до начала цикла, LL — длина цикла, bb — сколько slow прошёл внутри цикла до встречи.

К моменту встречи slow сделал a+ba + b шагов, а fast — вдвое больше, 2(a+b)2(a + b). Разница a+ba + b — это целое число кругов, которые fast намотал сверху:

a+b=kL⇒a=kL−ba + b = kL \quad\Rightarrow\quad a = kL - b

Справа — ровно столько шагов, сколько нужно от точки встречи, чтобы дойти до начала цикла (с точностью до целых кругов). Значит, указатель из head и указатель из точки встречи, шагая по одному, через aa шагов окажутся в одном узле — начале цикла.

Проверим на примере выше: хвост 1 → 2 (a=2a = 2), цикл 3 → 4 → 5 → 6 (L=4L = 4).

Шагslowfast
123
235
343
455 ← встреча

slow прошёл в цикле b=2b = 2 узла (3 → 4 → 5). Из узла 5 до начала цикла: 5 → 6 → 3 — два шага, ровно aa. Вторая фаза: из head указатель идёт 1 → 2 → 3, из точки встречи 5 → 6 → 3. Встретились в узле 3.

Длина цикла

Бонус: после встречи длину цикла можно посчитать, пройдя один круг от точки встречи.

def cycle_length(meet): length = 1 node = meet.next while node is not meet: node = node.next length += 1 return length

Для примера выше вернёт 4.

Happy Number: цикл без списка

Здесь паттерн проявляется во всей красе. LeetCode 202: число называется «счастливым», если повторная замена его на сумму квадратов цифр приводит к 1. Например:

19→12+92=82→68→100→119 \to 1^2 + 9^2 = 82 \to 68 \to 100 \to 1

А число 2 застревает в цикле:

2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...

Никакого связного списка нет, но есть функция next_number(x), и каждое число однозначно задаёт следующее. Это и есть неявный связный список: узлы — числа, next — функция. Последовательность либо приходит в 1 (а 1 переходит в себя — это цикл длины 1), либо зацикливается где-то ещё.

Почему она обязательно зацикливается и не уходит в бесконечность? Для числа из dd цифр сумма квадратов не больше 81d81d. Для трёхзначных это максимум 243243, а для числа из 13 девяток — всего 10531053. Большие числа быстро «сдуваются» до трёхзначных, а дальше значений конечное число — значит, какое-то повторится.

Решение «в лоб» — складывать встреченные числа в множество. Решение без памяти — быстрый и медленный указатели:

def is_happy(n: int) -> bool: def next_number(x: int) -> int: total = 0 while x: x, digit = divmod(x, 10) total += digit * digit return total slow = n fast = next_number(n) while fast != 1 and slow != fast: slow = next_number(slow) fast = next_number(next_number(fast)) return fast == 1 print(is_happy(19), is_happy(2), is_happy(7)) # True False True

Обратите внимание: fast стартует на шаг впереди. Если бы оба начинали с n, условие slow != fast было бы ложным сразу. Альтернатива — цикл do-while: сначала шаг, потом проверка.

Последовательность из 1 застревает на 1, поэтому если число счастливое, fast первым до неё доберётся, и проверка fast != 1 остановит цикл.

Find the Duplicate Number: массив как список

LeetCode 287 — задача, на которой многие впервые видят, насколько паттерн универсален. Дан массив nums из n+1n + 1 числа, каждое от 1 до nn. Ровно одно значение повторяется (возможно, много раз). Найти его, не меняя массив и используя O(1)O(1) памяти.

Сортировка меняет массив, множество требует O(n)O(n) памяти. Ключевой трюк: считать nums[i] указателем на индекс nums[i]. Получается функция i→nums[i]i \to nums[i] — тот же неявный список.

  • Индекс 0 никто не указывает (значения от 1), поэтому из него начинается «хвост».
  • Повторяющееся значение — это индекс, на который указывают два разных элемента. В связном списке так выглядит ровно одно место: вход в цикл.

Значит, ответ — начало цикла, и вторая фаза Флойда находит его:

def find_duplicate(nums: list[int]) -> int: slow = fast = nums[0] while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break slow = nums[0] while slow != fast: slow = nums[slow] fast = nums[fast] return slow print(find_duplicate([1, 3, 4, 2, 2])) # 2 print(find_duplicate([3, 1, 3, 4, 2])) # 3 print(find_duplicate([2, 2, 2, 2, 2])) # 2

Разберём [1, 3, 4, 2, 2]: из индекса 0 идём в 1, из 1 — в 3, из 3 — в 2, из 2 — в 4, из 4 — снова в 2. Цикл 2 → 4 → 2, вход в него — 2. На индекс 2 указывают nums[3] и nums[4] — это и есть дубликат.

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

Палиндромный связный список: середина + разворот

LeetCode 234: проверить, читается ли список одинаково в обе стороны, за O(1)O(1) памяти. Здесь быстрый и медленный указатели — только первый кирпичик:

  1. Найти конец первой половины (первую середину).
  2. Развернуть вторую половину.
  3. Пройти обе половины параллельно и сравнить.
  4. Развернуть вторую половину обратно — хороший тон, интервьюеры это ценят.
def reverse(head): prev = None while head: head.next, prev, head = prev, head, head.next return prev def is_palindrome(head) -> bool: if head is None or head.next is None: return True slow = fast = head while fast.next and fast.next.next: slow = slow.next fast = fast.next.next second = reverse(slow.next) p, q, result = head, second, True while q: if p.val != q.val: result = False break p, q = p.next, q.next slow.next = reverse(second) # восстанавливаем список return result print(is_palindrome(build([1, 2, 2, 1]))) # True print(is_palindrome(build([1, 2, 3, 2, 1]))) # True print(is_palindrome(build([1, 2, 3]))) # False

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

Сортировка списка: середина + слияние

Ещё одна связка — сортировка слиянием для связного списка (LeetCode 148). Середина делит список пополам, половины сортируются рекурсивно и сливаются:

def merge(a, b): dummy = tail = ListNode() while a and b: if a.val <= b.val: tail.next, a = a, a.next else: tail.next, b = b, b.next tail = tail.next tail.next = a or b return dummy.next def sort_list(head): if head is None or head.next is None: return head slow, fast = head, head.next # slow остановится на первой середине while fast and fast.next: slow = slow.next fast = fast.next.next right = slow.next slow.next = None return merge(sort_list(head), sort_list(right))

Здесь первая середина критична. Если взять вторую, то для списка из двух узлов левая половина окажется с двумя узлами, правая — пустой, и рекурсия никогда не закончится.

Когда паттерн подходит

Задайте себе вопрос: можно ли из текущего элемента однозначно получить следующий? Если да, у вас неявный связный список, и к нему применимы все приёмы выше.

Признак в условииЧто использовать
«есть ли цикл», «зацикливается ли процесс»встреча быстрого и медленного
«где начинается цикл», «найди повтор за O(1) памяти»вторая фаза Флойда
«середина списка», «раздели пополам»остановка fast на конце
«палиндром», «переупорядочить список»середина + разворот
последовательность xk+1=f(xk)x_{k+1} = f(x_k)Флойд на функции

Тот же алгоритм используется за пределами собеседований. Например, ρ-метод Полларда для факторизации чисел ищет цикл в последовательности x→x2+c(modn)x \to x^2 + c \pmod n именно черепахой и зайцем.

Есть и альтернатива — алгоритм Брента: «заяц» ждёт на месте, а «черепаха» телепортируется к нему через степени двойки. Он делает меньше вызовов функции, что важно, когда f дорогая. На собеседованиях его почти не спрашивают, но упомянуть — плюс.

Сложность

ЗадачаВремяПамять
Есть ли циклO(n)O(n)O(1)O(1)
Начало и длина циклаO(n)O(n)O(1)O(1)
Середина спискаO(n)O(n)O(1)O(1)
Happy NumberO(log⁡n)O(\log n)O(1)O(1)
Find the Duplicate NumberO(n)O(n)O(1)O(1)
Палиндромный списокO(n)O(n)O(1)O(1)

Для Happy Number первые шаги занимают O(log⁡n)O(\log n) — по числу цифр, а после того как число стало трёхзначным, длина последовательности ограничена константой.

Типичные ошибки

Проверка встречи до первого шага. Если написать if slow is fast в начале тела цикла, условие сработает сразу, ведь оба стартуют в head. Сначала шаг — потом проверка.

fast.next.next без проверки fast.next. На списке чётной длины получите AttributeError на None. Условие while fast and fast.next защищает оба обращения.

Сравнение значений вместо узлов. В связном списке пишите slow is fast (или === в JavaScript), а не slow.val == fast.val: в списке могут быть одинаковые значения в разных узлах. В Happy Number и Find the Duplicate, наоборот, узлы — это и есть числа, там сравнение по значению корректно.

Не та середина. Для разрезания списка нужна первая середина, для LeetCode 876 — вторая. Прогоняйте список из двух элементов.

Забыли восстановить список. После разворота второй половины исходный список испорчен. Если функция «только проверяет», это побочный эффект, который вызывающий код не ждёт.

Старт обоих указателей в одной точке в Happy Number. С циклом while slow != fast тело не выполнится ни разу. Либо двигайте fast вперёд заранее, либо используйте while True с break.

Что спрашивают на собеседованиях

Паттерн встречается в задачах уровня easy–medium, но follow-up вопросы бывают каверзными:

  • «Докажите, что указатели встретятся» — расстояние сокращается на 1 за шаг.
  • «Почему вторая фаза находит начало цикла?» — формула a=kL−ba = kL - b.
  • «Решите без дополнительной памяти» — типичный переход от множества к Флойду в Happy Number и Find the Duplicate.
  • «А если fast шагает на 3?» — встреча не гарантирована.
  • «Не изменяйте входные данные» — восстанавливайте список после разворота.

Хорошая стратегия на интервью: сначала озвучьте решение с множеством (O(n)O(n) памяти), потом предложите Флойда как оптимизацию. Так вы покажете, что понимаете компромисс, а не просто вспомнили трюк.

Что запомнить

  • Быстрый указатель шагает на 2, медленный на 1. Без цикла быстрый упирается в конец, в цикле — догоняет медленного.
  • Когда быстрый дошёл до конца, медленный стоит на середине. Условие цикла определяет, какая из двух середин.
  • После встречи переставьте один указатель в начало и идите с одной скоростью — встретитесь в начале цикла.
  • Паттерн работает на любой последовательности вида x→f(x)x \to f(x): числа (Happy Number), индексы массива (Find the Duplicate), остатки по модулю (метод Полларда).
  • Середина + разворот и середина + слияние — две связки, которые закрывают большую часть задач на связные списки.

Потренироваться в спокойной обстановке

Все задачи