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

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

Часть 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.

Часть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 продолжают двигаться со своими скоростями, точка их следующей встречи будет искомым результатом.

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

			LinkedListNode FindBegining(LinkedListNode head) {
	LinkedListNode slow = head;
	LinkedListNode fast = head;

	/*Находим первую точку встречи LOOP_SIZE-k шагов по связному списку.*/
	while (fast != null && fast.next != null) {
		slow = slow.next;
		fast = fast.next.next;
		if (slow == fast) { //Коллизия
			break;
		}
	}

	/* Ошибка - нет точки встречи, следовательно, нет петли */
	if (fast == null || fast.next == null) {
		return null;
	}

	/* Перемещаем медленный бегунок в начало списка (Head). Быстрый остается
	  в точке встречи.
	 *Каждые k шагов от Loop Start. Если указатели продолжат
	  движение с той же скоростью, то
	 * встретятся в точке Loop Start. */
	  slow = head;
	  while (slow != fast) {
	  	slow = slow.next;
	  	fast = fast.next;
	  }

	  /* Возвращаем точку начала петли. */
	  return fast;
}
		

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