re:re:actable
Урок 072 минуты чтения

Что такое fast and slow pointers?

На этой странице
Кратко

Fast and slow pointers - паттерн с двумя указателями, где один движется быстрее другого. Он часто используется для linked list: поиск середины, обнаружение цикла, определение начала цикла.

Вопрос

Что такое fast and slow pointers и как с их помощью найти цикл в списке?

Поиск середины linked list

type ListNode<T> = {
  value: T
  next: ListNode<T> | null
}
 
function middle<T>(head: ListNode<T> | null): ListNode<T> | null {
  let slow = head
  let fast = head
 
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
  }
 
  return slow
}

Когда fast дошел до конца, slow находится около середины.

Detect cycle

function hasCycle<T>(head: ListNode<T> | null): boolean {
  let slow = head
  let fast = head
 
  while (fast && fast.next) {
    slow = slow!.next
    fast = fast.next.next
 
    if (slow === fast) return true
  }
 
  return false
}

Это алгоритм Floyd cycle detection, его еще называют "черепаха и заяц".

Почему указатели обязательно встретятся? Если цикла нет, fast просто дойдет до null. Если цикл есть, оба указателя рано или поздно окажутся внутри него. С этого момента каждый шаг fast приближается к slow ровно на одну позицию: slow уходит вперед на 1, fast - на 2. Расстояние между ними уменьшается на 1 за шаг, поэтому fast не может "перепрыгнуть" slow и догонит его не более чем за длину цикла шагов.

1 -> 2 -> 3 -> 4 -> 5
          ^         |
          +---------+
 
шаг 1: slow=2, fast=3
шаг 2: slow=3, fast=5
шаг 3: slow=4, fast=4   встретились - цикл есть

Когда узнавать паттерн?

  • linked list;
  • найти середину;
  • определить cycle;
  • найти начало cycle;
  • удалить n-й элемент с конца;
  • сравнить две половины списка.

Что отвечать на собеседовании?

Fast and slow pointers используют два указателя с разной скоростью. Если fast двигается в два раза быстрее, то при достижении конца slow будет в середине. Если в списке есть цикл, fast рано или поздно догонит slow.

Что важно помнить: частые ошибки

  • Не проверять fast && fast.next.
  • Сравнивать values вместо node references.
  • Терять head при изменении списка.
  • Не понимать, почему указатели встретятся в цикле.
  • Не обрабатывать пустой список.

Мини-шпаргалка

  • Slow + fast.
  • Fast часто идет по 2 шага.
  • Middle list - классика.
  • Cycle detection - Floyd.
  • Сравнивай nodes, не values.
  • Проверяй null.

Документация

Wikipedia: Cycle detection (Floyd).

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам