Обзор

Быстрый и медленный указатели - это вариант паттерна двух указателей, где один указатель движется быстрее другого. Обычно медленный указатель делает один шаг, а быстрый - два.

Этот прием особенно часто встречается в задачах на связные списки. Он позволяет находить цикл, середину списка или точку встречи без дополнительной памяти.

Идея паттерна

Представим два указателя:

slow = head;
fast = head;

На каждой итерации:

slow = slow.next;
fast = fast.next.next;

Если в списке есть цикл, быстрый указатель рано или поздно догонит медленный. Если цикла нет, быстрый указатель дойдет до null.

Почему это работает

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

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

Когда использовать

Паттерн хорошо подходит, когда нужно:

1. Найти цикл в связном списке.

2. Найти середину связного списка.

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

4. Решить задачу на список с ограничением O(1) по дополнительной памяти.

5. Разделить список на две части.

Итоги

Быстрый и медленный указатели позволяют получать информацию о форме линейной структуры без хеш-множества и без изменения данных.