pattern heroPT–23LeetCode Extension

Быстрый и медленный указатели

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

Вариант
P13 Быстрый и медленный указателиЦикл · 1×

Пример задачи: проверить, есть ли в связном списке цикл.

head12345678slow
slowfastместо встречи

Ставим slow на голову списка: 1

slow = 1fast = –cycle = –
01/30
сначала · назад · пуск · шаг
Скорость
1function hasCycle(head):
2 slow = head
3 fast = head
4 cycle = false
5 while fast and fast.next are not none:
6 slow = slow.next
7 fast = fast.next.next
8 if slow is fast:
9 cycle = true
10 break
11 return cycle

← → шаг · пробел — пауза

Как узнать

связный список или любое правило «перейти к следующему» и вопрос про цикл, его начало или середину, часто с O(1) дополнительной памяти.

Как решать такие задачи

  1. Поставь оба указателя на голову списка.
  2. На каждом шаге двигай slow на один узел, а fast на два. Сначала проверь, что fast и fast.next существуют.
  3. Если fast дошёл до конца, цикла нет. В этот момент slow стоит на середине.
  4. Если они встретились, цикл есть. Чтобы найти его начало, верни один указатель на голову и двигай оба по одному узлу до новой встречи.

Вариант: Середина

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

  1. Поставь оба указателя на голову списка.
  2. Повторяй, пока есть fast и fast.next: двигай slow на один узел, а fast на два.
  3. Когда цикл закончился, slow стоит на середине. При нечётной длине fast останавливается на последнем узле, при чётной уходит на none, а slow оказывается на втором из двух средних узлов.
  4. Тем же приёмом список делят пополам: чтобы проверить, палиндром ли он, разверни половину после середины и сравни; чтобы отсортировать, отсортируй обе половины и слей их.

Вариант: На расстоянии n

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

  1. Как узнать: позиция в связном списке считается от конца, а пройти нужно один раз или длина неизвестна.
  2. Поставь перед головой фиктивный узел dummy и начни с него оба указателя.
  3. Сдвинь fast на n шагов в одиночку. Потом двигай оба по одному, пока fast.next не станет none.
  4. Теперь slow стоит прямо перед n-м узлом с конца: сделай slow.next = slow.next.next и верни dummy.next.
  5. Так же поворачивают список на k: найди k-й узел с конца, разрежь список перед ним и прицепи старый хвост к старой голове. Сначала возьми k по модулю длины.

Где встречается

  • Разложение чисел на множители. Ро-метод Полларда строит последовательность чисел, которая рано или поздно зацикливается, и находит цикл медленным и быстрым указателями, не храня сами числа. Он есть, например, в SymPy.
  • Криптография. Поллард приспособил ро-метод и к дискретному логарифму, и это лучшая известная общая атака на криптографию на эллиптических кривых. Ключи длиной 256 бит выбирают как раз так, чтобы ей не хватило времени.