Обнаружение цикла в связанном списке с подходом Hare and Tortoise

Ответ 1

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

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

С учетом этого рассмотрим две возможности:

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

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

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

♛ = 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 ступенях, заяц может завершить два раунда за это время. Даже если заяц пропустил черепаху в своем первом раунде (что будет), он определенно собирается догнать черепаху во втором раунде.

Ответ 2

Пусть итераторы A и B проходят через список соответственно по единицам и по двум. Consdier существует петля. Тогда в момент, когда 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) итераций.

Ответ 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;