Реализуйте алгоритм для однонаправленного списка с петлёй, возвращающий начальный узел петли

Эта задача является разновидностью классической задачи, задаваемой на собеседованиях, — определить, содержит ли связный список петлю. Давайте используем подход «Сопоставление с образцом».

Часть 1. Определяем, есть ли в связном списке петля

Простейший способ выяснить есть ли в связном списке петля,— использовать метод бегунка (быстрый/медленный). FastRunner делает два шага за один такт, а SlowRunner — только один. Подобно двум гоночным автомобилям, мчащимся по одной трассе разными путями, они непременно должны встретиться.

Проницательный читатель может задать вопрос: может ли быстрый бегунок «перепрыгнуть» медленный без столкновения? Это невозможно. Допустим, что FastRunner перепрыгнул через SlowRunner и теперь находится в элементе i+1 (а медленный – в i). Это означает, что на предыдущем шаге SlowRunner был в точке i-1, а FastRunner — ((i+1)-2)=i-1. Следовательно, столкновение неизбежно.

Часть 2. Когда же они встретятся?

Давайте введем обозначение: k – длина связного списка в разомкнутом виде. Как узнать, когда FastRunner и SlowRunner встретятся, используя алгоритм из части 1?

Мы знаем, что FastRunner перемещается в два раза быстрее, чем SlowRunner. Поэтому когда SlowRunner через k шагов попадет в петлю, FastRunner пройдет 2k шагов. Поскольку k существенно больше, чем длина петли, введем обозначение K=mod(k, LOOP_SIZE).

В каждом последующем шаге FastRunner и SlowRunner становятся на шаг (или два шага) ближе к цели. Поскольку система замкнута, когда A перемещается на  q, оно становится на q шагов ближе к B.

Можно установить следующие факты:

  1. SlowRunner: 0 шагов внутри петли.
  2. FastRunner: k шагов.
  3. SlowRunner: отстает от FastRunner на k шагов.
  4. FastRunner: отстает от SlowRunner на LOOP_SIZE – K шагов.
  5. FastRunner нагоняет SlowRunner со скоростью 1 шаг за единицу времени.

Когда же они встретятся? Если FastRunner на LOOP_SIZE – K  шагов отстает от SlowRunner, а FastRunner нагоняет его со скоростью 1 шаг за единицу времени, они встретятся через LOOP_SIZE- k шагов. В этой точке они будут отстоять на k шагов от начала петли. Давайте назовем эту точку CollisionSpot.

 

1

Часть3. Как найти начало петли?

Мы теперь знаем, что CollisonSpot – это k узел до начала петли. Поскольку K=mod(k, LOOP_SIZE) (или k=K+M*LOOP_SIZE для любого целого  M),  можно сказать, что до начала петли k узлов. Если узел N-2 узла в петле из 5 элементов, то элементы 7, 12 и даже 397 принадлежать петле.

Поэтому и CollisionSpot, и LinkedListHead находятся в k узлах от начала петли.

Если мы сохраним один указатель в CollisionSpot и переместим другой в LinkedListHead, то каждый из них будет отстоять на k узлов от LoopStart. Перемещение этих указателей заставит их столкнуться — на сей раз через k шагов – в точке LoopStart. Все, что нам нужно сделать, — возвратить этот узел.

Часть 4. Собираем все воедино

FastPointer двигается в два раза быстрее, чем SlowPointer. Через k узлов SlowPointer оказывается в петле, а FastPointer – на k-м узле связного списка. Это означает, что FastPointer и SlowPointer отделяют друг от друга LOOP_SIZE-k узлов.

Если FastPointer двигается на 2 узла за одиночный шаг SlowPointer, указатели будут сближаться на каждом цикле и встретятся через LOOP_SIZE-k циклов. В этой точке они окажутся на расстоянии k узлов от начала петли.

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

Давайте запишем алгоритм, воспользовавшись информацией из частей 1-3:

  1. Создадим два указателя FastPointer и SlowPointer.
  2. Будем перемещать FastPointer на 2 шага, а SlowPointer на один шаг.
  3. Когда указатели встретятся, нужно передвинуть SlowPointer в LinkedListHead, а FastPointer оставить на том же месте.
  4. SlowPointer и FastPointer продолжают двигаться со своими скоростями, точка их следующей встречи будет искомым результатом.

Следующий код реализует описанный алгоритм:

Разбор по книге «Карьера программиста. Как устроиться на работу в Google, Microsoft или другую ведущую IT – Компанию»