---
title: "Быстрый и медленный указатели"
url: https://algopath.pro/ru/patterns/fast-slow-pointers
language: ru
summary: "Один указатель делает по одному шагу за раз, а другой сразу по два. Именно разрыв между ними выдаёт циклы и середину списка."
updated: 2026-08-24
---

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

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

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

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

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

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

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

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

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

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

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

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

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

- **Два указателя (в одну сторону)** - Там один указатель читает, а другой пишет. Здесь читают оба, но с разной скоростью.
- **Хеш-множество / словарь** - Множество посещённых узлов тоже ловит цикл. Оно стоит O(n) памяти вместо O(1).
- **Разворот связного списка** - Разворот перевязывает сами ссылки. Этот приём не меняет в списке ни одного указателя.
- **Обход графа BFS / DFS** - Обход находит циклы в любом графе с множеством посещённых. Здесь работает то, что выход из узла один.

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

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

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

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

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

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

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

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

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

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

- **Проверяют в условии только быстрый указатель** Чтение fast.next.next падает, когда fast.next равен null. Проверяйте оба до шага.
- **Стартуют указатели с разных узлов** Фора меняет узел, на котором они встретятся. Доказательство про вход требует общего старта.
- **Сравнивают значения вместо узлов** Два разных узла могут хранить одно значение. Сравнивайте сами ссылки.
- **Считают точку встречи входом в цикл** Встреча происходит где-то внутри петли, а не в начале. Вход находит второй проход.

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

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

## JavaScript

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

## Python

```python
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
```

## PHP

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