Что такое 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.