Быстрый и медленный указатель: алгоритм Флойда, середина списка и Happy Number
Паттерн быстрого и медленного указателя: почему они встречаются в цикле, как найти середину списка и начало цикла, Happy Number и Find the Duplicate Number. Код на 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стоит ровно на середине; - после встречи переставили один указатель в начало и пошли с одинаковой скоростью — встретятся в начале цикла.
Ниже разбираем каждый вариант. Базовую задачу «есть ли цикл в списке» со всеми альтернативами (множество, модификация списка) мы подробно разбирали в статье Обнаружение цикла в связном списке — здесь сосредоточимся на самом паттерне и на задачах, где его не сразу узнаёшь.
Почему быстрый обязательно догонит медленного
Это главный вопрос, который задают на собеседовании после того, как вы написали код.
Пусть оба указателя уже внутри цикла длины . Расстояние от fast до slow по ходу движения — , где . За один шаг slow уходит вперёд на 1, а fast — на 2. Значит, расстояние между ними уменьшается ровно на 1 за каждый шаг:
Расстояние убывает по единице, поэтому «перепрыгнуть» через slow быстрый указатель не может. Встреча случится не позже чем через шагов после того, как slow вошёл в цикл.
Отсюда же оценка времени: до входа в цикл slow проходит шагов (длина «хвоста»), внутри — меньше . Итого .
А если
fastшагает на 3? Тогда расстояние уменьшается на 2 за шаг, и при нечётном и чётном указатели могут кружить, не встречаясь в одном узле. Скорости 1 и 2 — не традиция, а самый простой вариант, где встреча гарантирована.
Середина списка
Задача LeetCode 876 «Middle of the Linked List»: вернуть средний узел, а при чётной длине — второй из двух средних.
Наивный способ — пройти список, посчитать длину , затем пройти ещё шагов. Это тоже , но два прохода. Быстрый и медленный указатели делают то же самое за один: когда 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 = head | fast and fast.next | 4 (вторая) | 3 |
slow = fast = head | fast.next and fast.next.next | 3 (первая) | 3 |
slow = head, fast = head.next | fast and fast.next | 3 (первая) | 3 |
Не пытайтесь запомнить таблицу — проще за 10 секунд прогнать в голове список из двух элементов. Это лучший тест на off-by-one в задачах с серединой.
Начало цикла
LeetCode 142 «Linked List Cycle II»: если цикл есть, вернуть узел, с которого он начинается.
Алгоритм Флойда делает это в две фазы:
- Быстрый и медленный указатели идут до встречи.
- Один указатель переставляем в
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, — как раз случай «быстрый дошёл до конца».
Почему вторая фаза работает
Обозначим: — длина хвоста до начала цикла, — длина цикла, — сколько slow прошёл внутри цикла до встречи.
К моменту встречи slow сделал шагов, а fast — вдвое больше, . Разница — это целое число кругов, которые fast намотал сверху:
Справа — ровно столько шагов, сколько нужно от точки встречи, чтобы дойти до начала цикла (с точностью до целых кругов). Значит, указатель из head и указатель из точки встречи, шагая по одному, через шагов окажутся в одном узле — начале цикла.
Проверим на примере выше: хвост 1 → 2 (), цикл 3 → 4 → 5 → 6 ().
| Шаг | slow | fast |
|---|---|---|
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| 3 | 4 | 3 |
| 4 | 5 | 5 ← встреча |
slow прошёл в цикле узла (3 → 4 → 5). Из узла 5 до начала цикла: 5 → 6 → 3 — два шага, ровно . Вторая фаза: из 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. Например:
А число 2 застревает в цикле:
2 → 4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4 → ...
Никакого связного списка нет, но есть функция next_number(x), и каждое число однозначно задаёт следующее. Это и есть неявный связный список: узлы — числа, next — функция. Последовательность либо приходит в 1 (а 1 переходит в себя — это цикл длины 1), либо зацикливается где-то ещё.
Почему она обязательно зацикливается и не уходит в бесконечность? Для числа из цифр сумма квадратов не больше . Для трёхзначных это максимум , а для числа из 13 девяток — всего . Большие числа быстро «сдуваются» до трёхзначных, а дальше значений конечное число — значит, какое-то повторится.
Решение «в лоб» — складывать встреченные числа в множество. Решение без памяти — быстрый и медленный указатели:
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 из числа, каждое от 1 до . Ровно одно значение повторяется (возможно, много раз). Найти его, не меняя массив и используя памяти.
Сортировка меняет массив, множество требует памяти. Ключевой трюк: считать nums[i] указателем на индекс 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: проверить, читается ли список одинаково в обе стороны, за памяти. Здесь быстрый и медленный указатели — только первый кирпичик:
- Найти конец первой половины (первую середину).
- Развернуть вторую половину.
- Пройти обе половины параллельно и сравнить.
- Развернуть вторую половину обратно — хороший тон, интервьюеры это ценят.
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 на конце |
| «палиндром», «переупорядочить список» | середина + разворот |
| последовательность | Флойд на функции |
Тот же алгоритм используется за пределами собеседований. Например, ρ-метод Полларда для факторизации чисел ищет цикл в последовательности именно черепахой и зайцем.
Есть и альтернатива — алгоритм Брента: «заяц» ждёт на месте, а «черепаха» телепортируется к нему через степени двойки. Он делает меньше вызовов функции, что важно, когда f дорогая. На собеседованиях его почти не спрашивают, но упомянуть — плюс.
Сложность
| Задача | Время | Память |
|---|---|---|
| Есть ли цикл | ||
| Начало и длина цикла | ||
| Середина списка | ||
| Happy Number | ||
| Find the Duplicate Number | ||
| Палиндромный список |
Для Happy Number первые шаги занимают — по числу цифр, а после того как число стало трёхзначным, длина последовательности ограничена константой.
Типичные ошибки
Проверка встречи до первого шага. Если написать 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 за шаг.
- «Почему вторая фаза находит начало цикла?» — формула .
- «Решите без дополнительной памяти» — типичный переход от множества к Флойду в Happy Number и Find the Duplicate.
- «А если fast шагает на 3?» — встреча не гарантирована.
- «Не изменяйте входные данные» — восстанавливайте список после разворота.
Хорошая стратегия на интервью: сначала озвучьте решение с множеством ( памяти), потом предложите Флойда как оптимизацию. Так вы покажете, что понимаете компромисс, а не просто вспомнили трюк.
Что запомнить
- Быстрый указатель шагает на 2, медленный на 1. Без цикла быстрый упирается в конец, в цикле — догоняет медленного.
- Когда быстрый дошёл до конца, медленный стоит на середине. Условие цикла определяет, какая из двух середин.
- После встречи переставьте один указатель в начало и идите с одной скоростью — встретитесь в начале цикла.
- Паттерн работает на любой последовательности вида : числа (Happy Number), индексы массива (Find the Duplicate), остатки по модулю (метод Полларда).
- Середина + разворот и середина + слияние — две связки, которые закрывают большую часть задач на связные списки.