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

Быстрый и медленный указатели: как это работает?

Поставьте оба указателя на голову. Один делает шаг за раунд, другой два.

Двигайте их вместе в одном цикле. Остановитесь, когда быстрый уйдёт за конец.

Если список кончился, цикла нет. Ссылка null это доказательство.

Если цикл есть, быстрый указатель обгоняет медленный на круг. Они окажутся на одном узле.

Внутри цикла разрыв сокращается на единицу за раунд. Поэтому встреча гарантирована.

Когда быстрый доходит до конца, медленный стоит на середине. Середина достаётся бесплатно.

1. slow = 1, fast = 1Список от 1 до 5. Оба указателя стартуют с головы.
2. slow = 2, fast = 3Один шаг против двух. Разрыв составляет один узел.
3. slow = 3, fast = 5Разрыв стал два. Быстрый почти вышел за конец.
4. fast.next равен nullСписок кончился, значит цикла нет.
5. slow = 3Медленный стоит на среднем узле. Пять узлов, середина третья.

function hasCycle(head) {
    let slow = head;
    let fast = head;
    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;
        if (slow === fast) return true;
    }
    return false;
}

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

Где начинается цикл

Связный список может где-то заворачиваться сам в себя. Верните узел, с которого начинается петля.

Если петли нет, верните null.

Сначала дайте медленному и быстрому указателям встретиться внутри петли.

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

function detectCycle(head) {
    let slow = head;
    let fast = head;

    while (fast && fast.next) {
        slow = slow.next;
        fast = fast.next.next;

        if (slow === fast) {
            // head to entry is the same distance as meeting point to entry
            let walker = head;
            while (walker !== slow) {
                walker = walker.next;
                slow = slow.next;
            }
            return walker;
        }
    }

    return null;
}

Быстрый и медленный указатели: когда применять?

Эти формулировки в условии ведут сюда:

• •обнаружить цикл в связном списке
• •найти, где начинается цикл
• •найти средний узел списка
• •определить, является ли список палиндромом
• •без доп. памяти / O(1) память, только указатели

Быстрый и медленный указатели: с чем путают?

• Два указателя (в одну сторону) (Two pointers (same direction)): Там один указатель читает, а другой пишет. Здесь читают оба, но с разной скоростью.
• Хеш-множество / словарь (Hash set / map): Множество посещённых узлов тоже ловит цикл. Оно стоит O(n) памяти вместо O(1).
• Разворот связного списка (Linked list reversal): Разворот перевязывает сами ссылки. Этот приём не меняет в списке ни одного указателя.
• Обход графа BFS / DFS (Graph BFS / DFS): Обход находит циклы в любом графе с множеством посещённых. Здесь работает то, что выход из узла один.

Быстрый и медленный указатели: частые ошибки

• Проверяют в условии только быстрый указатель

  Чтение fast.next.next падает, когда fast.next равен null. Проверяйте оба до шага.

• Стартуют указатели с разных узлов

  Фора меняет узел, на котором они встретятся. Доказательство про вход требует общего старта.

• Сравнивают значения вместо узлов

  Два разных узла могут хранить одно значение. Сравнивайте сами ссылки.

• Считают точку встречи входом в цикл

  Встреча происходит где-то внутри петли, а не в начале. Вход находит второй проход.

Быстрый и медленный указатели: задачи с собеседований

• Цикл в связном списке: Сама встреча и есть весь ответ.
• Цикл в связном списке II: Второй проход от головы находит место входа.
• Середина связного списка: Когда быстрый кончил, медленный стоит на середине.
• Счастливое число: Шаг с суммой квадратов цифр строит невидимый связный список.
• Найти дубликат: Значения массива работают как ссылки на следующий узел.
• Палиндром в связном списке: Найдите середину, разверните заднюю часть, сравните.
• Удалить n-й узел с конца: Здесь фиксированный разрыв, а не двойная скорость.

Быстрый и медленный указатели: сложность по времени и памяти

O(n)

n до 1e6 даёт O(n) времени и O(1) памяти. Медленный указатель делает не больше n шагов.