Алгоритмы с нуля

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

Суть Используй два указателя, двигающихся с разными скоростями, чтобы найти середину списка, обнаружить циклы (метод черепахи и зайца Флойда) и доказать, что указатели встретятся внутри любого цикла. Метод решает сложные задачи связных списков с O(1) памятью.

◷ 24 min

В прошлом уроке ты развернул связный список обновляя указатели один за другим. Сегодня ты выучишь другой трюк с указателями: отправь два указателя вниз по списку с разными скоростями. Медленный указатель движется один шаг; быстрый указатель движется два. Если в списке есть цикл, указатели встретятся. Если список линейный (нет цикла), быстрый указатель упадёт с конца. Эта методика — названная метод черепахи и зайца — может найти средний узел и обнаружить циклы только с O(1) дополнительной памятью.

Цель

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

Идея

Основная идея: два указателя с разными скоростями

Представь прогулку вниз по дорожке с другом. Ты ходишь один шаг в секунду; твой друг ходит два шага в секунду. Если дорожка линейна (имеет конец), твой друг достигает конца пока ты всё ещё в середине. Если дорожка зацикливается назад на себя, твой друг обогнёт тебя — в конце концов твой друг доловит тебя и вы встретитесь снова.

В связном списке мы используем два указателя (медленный и быстрый) чтобы моделировать это:

Медленный указатель: Движется один шаг за итерацию (на следующий узел).
Быстрый указатель: Движется два шага за итерацию (пропускает один узел, идёт на два дальше).

медленный: 1 шаг
быстрый: 2 шага

Поиск среднего узла

Дан список [10] → [20] → [30] → [40] → [50], что такое середина?

Используй два указателя, оба начинают с head. На каждой итерации:

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

Начало: медленный = 10, быстрый = 10
После 1: медленный = 20, быстрый = 30
После 2: медленный = 30, быстрый = 50

Цикл выходит потому что быстрый.next это null.
медленный находится на 30, в середине.

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

Обнаружение цикла: алгоритм черепахи и зайца

Цикл означает список в конце концов зацикливается назад на более ранний узел. Пример: [10] → [20] → [30] → [20] (указатель 30 указывает назад на 20, создавая цикл).

Используя два указателя с разными скоростями, если есть цикл:

Медленный движется один шаг за итерацию.
Быстрый движется два шага за итерацию.
Если быстрый когда-нибудь достигает null, нет цикла.
Если быстрый и медленный когда-нибудь указывают на один узел, есть цикл.

Почему они встретятся? В цикле, быстрый указатель наогнал медленного на один шаг за итерацию (он движется на два пока медленный движется на один). В конце концов, быстрый обогнёт медленного.

Пример цикла: [1] → [2] → [3] → [4] → [5] → [3] (зацикливается назад на 3)

Начало: медленный = 1, быстрый = 1
Итер 1: медленный = 2, быстрый = 3
Итер 2: медленный = 3, быстрый = 5
Итер 3: медленный = 4, быстрый = 4 (быстрый поймал медленного! Цикл обнаружен.)

Почему они встретятся внутри цикла

Предположим цикл имеет длину c (число узлов в цикле). Когда медленный входит в цикл:

Быстрый впереди и движется в два раза быстрее.
Каждая итерация, быстрый наогнал медленного на один шаг (движется на 2, медленный движется на 1).
Промежуток между ними уменьшается на 1 каждый шаг.
В конце концов промежуток становится 0, и они встречаются.

Ключевой факт: Они встречаются где-то внутри цикла, никогда снаружи. Это потому что как только медленный входит в цикл, он никогда не выходит; быстрый всегда впереди, так что он уже внутри. В конце концов быстрый ловит медленного.

Важное замечание: Это обнаруживает цикл существует, но не говорит где он начинается.

Чтобы найти начало цикла (первый узел цикла), ты нуждаешься в втором проходе:

После обнаружения цикла, помести один указатель на head.
Помести другой указатель где медленный и быстрый встретились.
Двигай оба со скоростью 1 (один шаг каждую итерацию).
Они встречаются в начале цикла.

(Мы не будем кодировать это подробно — это последующая методика — но это важно знать ограничение.)

Код

Поиск среднего узла:

function findMiddle(head) {
  let slow = head;
  let fast = head;
  
  // Двигай быстрый два шага, медленный один, пока быстрый достигает конца
  while (fast !== null && fast.next !== null) {
    slow = slow.next;         // Двигай медленный один шаг
    fast = fast.next.next;    // Двигай быстрый два шага
  }
  
  return slow;  // slow находится в середине
}

Обнаружение цикла (черепаха и заяц):

function hasCycle(head) {
  if (head === null || head.next === null) return false;
  
  let slow = head;
  let fast = head;
  
  // Если есть цикл, быстрый в конце концов поймает медленного
  while (fast !== null && fast.next !== null) {
    slow = slow.next;         // Двигай медленный один шаг
    fast = fast.next.next;    // Двигай быстрый два шага
    
    if (slow === fast) {
      return true;  // Цикл обнаружен
    }
  }
  
  return false;  // быстрый достигает конца; нет цикла
}

Попробуй оба алгоритма интерактивно:

class Node {
constructor(value, next = null) {
  this.value = value;
  this.next = next;
}
}

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

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

return slow;
}

function hasCycle(head) {
if (head === null || head.next === null) return false;

let slow = head;
let fast = head;

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

return false;
}

// Тест 1: Найди середину [10, 20, 30, 40, 50]
let head = new Node(10);
head.next = new Node(20);
head.next.next = new Node(30);
head.next.next.next = new Node(40);
head.next.next.next.next = new Node(50);

const middle = findMiddle(head);
console.log("Середина [10, 20, 30, 40, 50] это:", middle.value);

// Тест 2: Нет цикла
console.log("Цикл в [10, 20, 30, 40, 50]?", hasCycle(head));

// Тест 3: Цикл — сделай узел 50 указывать назад на узел 30
const node30 = head.next.next;
head.next.next.next.next.next = node30;  // 50 → 30

console.log("Цикл после создания цикла?", hasCycle(head));

Вывод

Пошаговый разбор

Давай проследим поиск середины [10] → [20] → [30] → [40] → [50] используя два указателя.


      1
      let slow = head;
    

      2
      let fast = head;
    

      3
      while (fast !== null && fast.next !== null) {
    

      4
        slow = slow.next;
    

      5
        fast = fast.next.next;
    

      6
      }

Теперь проследи обнаружение цикла: [1] → [2] → [3] → [4] → [3] (цикл назад на 3).


      1
      let slow = head;
    

      2
      let fast = head;
    

      3
      while (fast !== null && fast.next !== null) {
    

      4
        slow = slow.next;
    

      5
        fast = fast.next.next;
    

      6
        if (slow === fast) return true;
    

      7
      }

Сложность

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

Операция	Время	Пространство
Поиск середины списка	O(n)	O(1)
Обнаружение цикла (черепаха и заяц)	O(n)	O(1)
Поиск начала цикла	O(n)	O(1)

Почему O(n) для всех? Мы посещаем каждый узел в списке один раз (или пока мы не обнаружим цикл). Быстрый указатель достигает конца быстрее, но мы всё ещё итерируем через структуру списка.

Почему O(1) пространство? Мы только используем два указателя — константное пространство, не hash set, не массив.

Сравни с наивным обнаружением цикла: Используя hash set чтобы хранить посещённые узлы, также находит циклы в O(n) времени но стоит O(n) пространства. Два указателя достигают того же в O(1) пространстве.

Практика 0 / 5

В списке [10] → [20] → [30] → [40] → [50], какой узел это середина?

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

Связный список это [1] → [2] → [3] → [4] → [3] (next узла 4 указывает назад на 3). Что возвращает алгоритм черепахи и зайца?

Почему должны быстрый и медленный указатели встретиться в конце концов если есть цикл?

Список не имеет цикла: [10] → [20] → [30] → [40] → null. Что возвращает hasCycle?

Граничные случаи

Чётная против нечётной длины списков: Для списка чётной длины [10, 20, 30, 40], середина неоднозначна (это 20 или 30?). Большинство реализаций возвращают вторую середину (30) потому что когда быстрый падает с конца, медленный находится на позиции length/2 + 1. Будь в курсе этого когда используешь методику поиска середины.

Частая ошибка

«Быстрый указатель должен двигаться на 3 или 4 шага чтобы идти быстрее.» Нет. Быстрый должен двигаться ровно на 2 шага. Почему? Если быстрый движется на k > 2 шагов, он может прыгнуть над медленным указателем и никогда не поймает его, даже если есть цикл. Правило 2-шага гарантирует сходимость в цикле.

Ещё практика

Частое последующее: Дан список с циклом, найди первый узел цикла (где цикл начинается). Подсказка: После обнаружения цикла с медленным и быстрым, помести один указатель на head и другой где они встретились. Двигай оба один шаг за раз. Они встречаются в начале цикла. Это требует математического доказательства (связанное с длиной цикла и позиции где они встречаются), но алгоритм элегантен.

Проверь себя

Викторина

Почему методика двух указателей (быстрого-медленного) чтобы обнаружить цикл лучше чем использование hash set посещённых узлов?

Итог

Быстрый и медленный указатели (черепаха и заяц):

Основная идея: Используй два указателя продвигающихся с разными скоростями (медленный: 1 шаг, быстрый: 2 шага).
Поиск середины: Двигай оба указателя пока быстрый достигает конца. Медленный находится в середине (или вторая середина для чётно-длинных списков).
Обнаружение циклов: В списке с циклом, быстрый в конце концов обогнёт медленного. Если они когда-нибудь указывают на один узел, цикл существует.
Почему они встречаются в цикле: Быстрый наогнал медленного на 1 шаг каждую итерацию. В конечном цикле, промежуток сужается пока не станет 0.
Преимущество пространства: O(1) дополнительно пространства vs O(n) для hash set, оба в O(n) времени.
Быстрый должен двигаться на 2, не 3 или 4: Только 2 шага гарантирует сходимость в цикле.
Замечание: Это обнаруживает циклы но не прямо определяет где цикл начинается. Второй проход необходим для этого.

Далее ты выучишь стеки и очереди — две структуры данных построенные на списках что налагают правила на как и когда ты можешь добавлять и удалять элементы. Эти инструменты необходимы для парсинга, undo/redo, и поиска в ширину.

Продолжить восхождение ↑Стек