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

Fast & slow pointers

O(n)

Один указатель делает по одному шагу за раз, а другой сразу по два. Именно разрыв между ними выдаёт циклы и середину списка.

Elman HuseynovОбновлено 17 окт. 2026 г.

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

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

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

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

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

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

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

Источники: Википедия: Нахождение цикла

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

Поиск цикла в связном списке медленным и быстрым указателями

hasCycle(1 → 2 → 3 → 4 → 5 → 6 → back to 3)

round = 0slow = 1fast = 1

Есть ли в списке цикл? Последний узел, 6, указывает обратно на 3. Оба указателя стоят на голове.

1 / 10

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

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;
}

interface ListNode {
    val: number;
    next: ListNode | null;
}

function hasCycle(head: ListNode | 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;
}

def has_cycle(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        if slow is fast:
            return True
    return False

function hasCycle(?Node $head): bool {
    $slow = $head;
    $fast = $head;
    while ($fast !== null && $fast->next !== null) {
        $slow = $slow->next;
        $fast = $fast->next->next;
        if ($slow === $fast) return true;
    }
    return false;
}

    public static boolean hasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    public static class ListNode {
        public int val;
        public ListNode next;
    }

    public static bool HasCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) return true;
        }
        return false;
    }

    public class ListNode {
        public int val;
        public ListNode next;
    }

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

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

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

Если петли нет, верните 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(n).

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

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

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

Паттерн «Быстрый и медленный указатели» чаще всего путают с этими паттернами: Два указателя (в одну сторону), Хеш-множество / словарь, Разворот связного списка и Обход графа BFS / DFS.

Два указателя (в одну сторону) (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-й узел с конца.

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