Detección de ciclo en la lista vinculada con el enfoque Hare and Tortoise

Question

Entiendo que para detectar un ciclo en una lista vinculada puedo usar el enfoque Hare and Tortoise, que tiene 2 punteros (lento y rápido). Sin embargo, después de leer en wiki y otros recursos, no entiendo por qué está garantizado que los dos punteros se encontrarán en O (n) complejidad de tiempo.

Answer 1

Aquí hay un intento de prueba informal.

La forma del ciclo no es importante. Puede tener una cola larga y un bucle hacia el final, o simplemente un bucle desde el principio hasta el final sin una cola. Independientemente de la forma del ciclo, una cosa está clara: que el puntero de tortuga no puede alcanzar al puntero de liebre. Si los dos se encontraran alguna vez, el puntero de liebre debe alcanzar el puntero de la tortuga desde atrás.

con lo establecido, tenga en cuenta las dos posibilidades:

1. puntero liebre es un paso detrás del puntero de tortuga.
2. indicador de liebre está dos pasos detrás del puntero de la tortuga.

Todas las distancias mayores se reducirán a una o dos al final.

Suponiendo que el puntero de tortuga siempre se mueve primero (también puede ser al revés), en el primer caso, el puntero de tortuga avanza un paso adelante. Ahora la distancia entre ellos es 2. Cuando el puntero de liebre da 2 pasos ahora, aterrizarán en el mismo nodo. Aquí está lo mismo ilustrado para una comprensión más fácil. Demasiado texto puede interponerse en el camino.

 
♛ = 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! 

Ahora vamos a considerar el segundo caso en el que la distancia entre ellos es de 2. El puntero se mueve lenta un paso adelante y la distancia entre ellos se convierte en 3. A continuación, el puntero rápido avanza dos pasos y la distancia entre ellos se reduce a 1, que es idéntico al primer caso en el que ya hemos demostrado que se encontrarán en un paso más. De nuevo, ilustrado para una comprensión más fácil.

 
.♛.♙... #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. 

Ahora, en cuanto a porqué este algoritmo se garantiza que sea en O (n), utilizar lo que ya hemos establecido que la liebre se satisfacer la tortuga antes de que se mueve por delante. Lo que significa que una vez que ambos estén dentro del bucle, antes de que la tortuga complete otra ronda, se encontrará con la liebre ya que la liebre se mueve dos veces más rápido. En el peor de los casos, el ciclo será un círculo con n nodos. Mientras que la tortuga solo puede completar una ronda en n pasos, la liebre puede completar dos rondas en ese momento. Incluso si la liebre se perdió la tortuga en su primera ronda (que lo hará), definitivamente va a alcanzar a la tortuga en su segunda ronda.

Answer 2

Deje que los iteradores A y B revisen la lista respectivamente por unidades y de a dos. Consdier existe un bucle. Entonces, en el momento en que A ingrese al ciclo, B ya estará en algún lugar dentro de él. Si la longitud del bucle es K, entonces B se ejecutará alrededor de él en ]K/2[ se mueve, por lo que en la mayoría de 2*]K/2[ iteraciones obtendremos una situación en la B aparece detrás A en una distancia 1: B->A o 2: B->.->A, y es B 'th turno. Después de esto, obviamente, se encontrarán ya sea en 1 o 2 movimientos. Entonces, si el ciclo existe y comienza en alguna posición P, entonces hacemos como máximo 2*P + 2*]K/2[ + 2 = O(N) iteraciones.

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;