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

Две ссылки, разные скорости

Техника fast and slow pointers использует две ссылки, которые стартуют в одной цепочке, но двигаются с разной скоростью. Медленный указатель обычно делает один шаг, а быстрый — два. Разница в пройденном расстоянии позволяет получать информацию о структуре списка без массива индексов и без дополнительного прохода для подсчёта длины.

Поиск середины списка

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

Node slow = head;
Node fast = head;

while (fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
}

Node middle = slow;

Оба указателя проходят только вперёд, поэтому алгоритм работает за O(n) и использует O(1) дополнительной памяти. При чётном количестве узлов этот вариант оставит slow на втором из двух центральных узлов.

Почему техника работает

После каждого шага цикла fast прошёл примерно вдвое больше узлов, чем slow. Значит, когда быстрый указатель исчерпал всю длину списка, медленный прошёл около половины этой длины.

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