Обнаружение цикла в связанном списке с помощью подхода «Заяц и черепаха»

Question

Я понимаю, что для обнаружения цикла в связанном списке я могу использовать подход «Заяц и черепаха», который содержит 2 указателя (медленный и быстрый). Однако после прочтения вики и других ресурсов я не понимаю, почему гарантируется, что два указателя будут встречаться в O (n) времени сложности.

Answer 1

Вот попытка неофициального доказательства.

Форма цикла не имеет значения. Он может иметь длинный хвост и петлю к концу или просто петлю от начала до конца без хвоста. Независимо от формы цикла ясно одно - указатель черепахи не может догнать указателя зайца. Если они когда-либо встретятся, указатель зайца должен догнать указатель черепахи сзади.

Установив это, рассмотрим две возможности:

1. указатель зайца - один шаг позади указателя черепахи.
2. указатель зайца находится в двух шагах от указателя черепахи.

Все большие расстояния со временем сократятся до одного или двух.

Если предположить, что указатель черепахи всегда перемещается первым (может быть и наоборот), то в первом случае указатель черепахи делает один шаг вперед. Теперь расстояние между ними равно 2. Когда указатель зайца делает 2 шага, они приземляются на одном узле. Вот то же самое, проиллюстрированное для облегчения понимания. Слишком много текста может помешать.

♛ = hare
♙ = tortoise
X = both meet

..♛♙... #1 - Initially, the hare is one step behind the tortoise.
..♛.♙.. #2 - Now the tortoise takes one step. now hare is two steps behind.
....X.. #3 - Next, the hare takes two steps and they meet!

Теперь давайте рассмотрим второй случай, когда расстояние между ними равно 2. Медленный указатель перемещается на один шаг вперед, а расстояние между ними становится равным 3. Затем быстрый указатель перемещается вперед на два шага, а расстояние между ними уменьшается до 1, что идентичен первому случаю, в котором мы уже доказали, что они встретятся еще на одном этапе. Опять же, проиллюстрировано для облегчения понимания.

.♛.♙... #1 - Initially, the hare is two steps behind the tortoise.
.♛..♙.. #2 - Now the tortoise takes one step and they become three steps apart.
...♛♙.. #3 - Next, the hare takes two steps which is identical to previous case.

Теперь, что касается того, почему этот алгоритм гарантированно находится в O (n), используйте то, что мы уже установили, что заяц встретит черепаху, прежде чем он продвинется вперед. Это означает, что как только оба окажутся внутри петли, прежде чем черепаха завершит еще один раунд, она встретит зайца, поскольку заяц движется в два раза быстрее. В худшем случае цикл будет кругом с n узлами. В то время как черепаха может завершить только один раунд за n шагов, заяц может пройти два раунда за это время. Даже если заяц пропустил черепаху в первом раунде (что он и сделает), он наверняка догонит черепаху во втором раунде.

Answer 2

Пусть итераторы A и B пройдут по списку соответственно по одному и по двое. У консьержа существует петля. Тогда в момент, когда A входит в цикл, B уже будет где-то внутри него. Если длина цикла равна K, то B будет обходить его за ]K/2[ ходов, поэтому не более чем при 2*]K/2[ итерациях мы получим ситуацию, когда B окажется позади A на расстоянии 1: B->A или 2: B->.->A, и наступил B-й ход. После этого, очевидно, они встретятся либо в 1, либо в 2 ходах. Итак, если цикл существует и начинается в некоторой позиции P, то мы делаем не более 2*P + 2*]K/2[ + 2 = O(N) итераций.

Answer 3

//if you just want to check if there is a loop

loop = false;
item = head-of-list; 
while (item != nil)
{
   if (item.next < 0) 
   {
      loop = true; 
      break; 
   }
   else
   {
      actual = item;
      item = item.next; 
      actual.next = actual.next * -1; 
   }
} 

return loop;