algorithm - simples - Prueba de detección del inicio del ciclo en la lista enlazada
operaciones con listas enlazadas (6)
Esta pregunta ya tiene una respuesta aquí:
Desde varios mensajes dentro de stackoverflow y fuera, he llegado a saber cómo detectar ciclos en una lista vinculada, la duración de un ciclo. También encontré el método sobre cómo detectar el inicio del bucle.
Aquí están los pasos de nuevo para referencia.
Bucle de detección:
Tienen dos punteros, clásicamente llamados liebre y tortuga. Mueva la liebre por 2 pasos y la tortuga por 1. Si se encuentran en algún punto, entonces seguramente hay un ciclo y el punto de reunión obviamente está dentro del ciclo.
Encontrando la longitud del Loop:
Mantenga un puntero fijo en el punto de reunión e incremente el otro hasta que vuelvan a ser los mismos. Incrementa un contador a medida que avanzas y el valor del contador en la reunión será la duración del ciclo.
Encuentra el inicio del ciclo.
Tome un puntero para comenzar de la lista y mantenga el otro en el punto de reunión. Ahora incrementa ambos por uno y el punto de encuentro es el comienzo del bucle. Verifiqué el método usando algunos casos en papel, pero no entiendo por qué debería funcionar.
¿Alguien puede proporcionar una prueba matemática de por qué este método funciona?
Distancia recorrida por slowPointer antes de la reunión = x + y
Distancia recorrida por fastPointer antes de la reunión = (x + y + z) + y = x + 2y + z
Como fastPointer viaja con el doble de la velocidad de slowPointer, y el tiempo es constante para ambos cuando llegan al punto de encuentro.
Entonces, utilizando una relación simple de velocidad, tiempo y distancia 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z
Por lo tanto, al mover slowPointer al inicio de la lista enlazada y al hacer que slowPointer y fastPointer muevan un nodo a la vez, ambos tienen la misma distancia que cubrir.
Alcanzarán el punto donde el bucle comienza en la lista enlazada.
La segunda parte, que dice que "para encontrar el inicio del bucle, simplemente mueva un puntero al inicio de la lista y luego itere ambos hasta que se encuentren", ¡está mal!
Solo es correcto si el puntero rápido ha recorrido el bucle exactamente una vez, es decir, que la parte anterior al inicio del bucle es más corta que la longitud del bucle, pero si es más larga, entonces el algoritmo no funciona; Puedes quedar atrapado en un bucle infinito.
Pruébelo con una lista enlazada con 11 elementos, donde el 11º apunta al 7º:
1 1 -> 3 2 -> 5 3 -> 7 4 -> 9 5 -> 11 6 -> 8 7 -> 10 8 -> 7 9 -> 9 9
- bucle detectado
Mueva uno hacia atrás para comenzar e incrementarlos: 1 9 -> 2 10 -> 3 11 -> 4 7 -> 5 8 -> 6 9 -> 7 10 -> 8 11 -> 9 7 -> 10 8 -> 11 9 -> 7 10 -> 8 11 -> ...
No lo creo, es cierto que cuando se encuentran, ese es el punto de partida. Pero sí, si el otro puntero (F) estaba en el punto de reunión anterior, ese puntero estará al final del bucle en lugar del inicio del bucle y el puntero (S) que comenzó desde el principio de la lista. Terminar al inicio del bucle. por ejemplo:
Comience F tan rápido y S tan lento que terminan reuniéndose a las 9. Ahora cuando empiezo la S desde el inicio otra vez, llegará al inicio del bucle, es decir, 7 pero f estará a 16 ..
por favor avisame si estoy equivocado
Si representa una lista con un puntero a su primer nodo ( lista )
El algoritmo para detectar bucles se describe a continuación:
- Declarar dos punteros ( pFast ) y ( pSlow ).
- Haz pSlow y pFast point to list .
- Hasta ( pSlow ), ( pFast ) o ambos apuntan a NULL:
- Si , luego se ha encontrado STOP como un bucle.
- Si se ha alcanzado este punto (uno o los dos punteros son NULL), no hay bucles en la lista.
Supongamos que este algoritmo es correcto. En este esquema, una situación de bucle se representa mediante el siguiente diagrama:
Observe cómo cada nodo, excepto el que apunta al comienzo de un bucle, está etiquetado con el número de su objetivo menos uno. Entonces, si un nodo está etiquetado con i y no es el comienzo de un bucle, entonces el nodo etiquetado con i-1 apunta como el siguiente elemento.
El algoritmo explicado anteriormente se puede describir como un bucle, ya que su paso principal (3) es un conjunto de subpasos que se repiten hasta que se cumple la condición de salida. Eso nos obliga a representar pFast y pSlow en función del número de iteración en la ejecución del algoritmo ( t ).
Si la lista no tuviera bucles, las posiciones de los punteros se describirían en función de t como:
Sin embargo, hay un nodo donde se inicia el bucle y esa función deja de describir la evolución de los punteros. Suponiendo que este puntero está etiquetado con m , que el bucle contiene nodos (es decir, y ), y estableciendo t = 0 como valor de iteración cuando entonces:
Si un puntero es realmente suficiente para detectar bucles usando el algoritmo descrito, entonces debe existir al menos una solución a la ecuación .
Esta ecuación es verdadera si y solo si hay un valor para t que hace:
Esto termina en una función, que genera valores de t que son soluciones válidas a la ecuación descrita anteriormente:
Por lo tanto, se demuestra que un puntero lento y un puntero rápido son suficientes para detectar condiciones de bucle en una lista enlazada.
Puede simplificar la prueba de ''Encontrar el inicio del ciclo'' si no usa el punto de encuentro.
Deje que el segundo puntero no comience en el ''punto de encuentro'', sino que M adelanta al primer puntero. (Donde M es la longitud del bucle.)
De esta manera, la prueba es bastante obvia. Cuando el primer puntero llega al inicio del bucle, el segundo será exactamente M pasos adelante: también al comienzo del bucle.
/* Algorithm : P2 is moving through the list twice as fast as P1.
If the list is circular, it will eventually get around P1 and meet */
public boolean hasCycle()
{
DoubleNode p1,p2;
p1=p2=firstNode; //Start with the first loop
try
{
while (p2 != null) //If p2 reaches end of linked list, no cycle exists
{
p1=p1.next; //Move to next
p2=p2.next.next; //Move to 2 steps next
if(p1==p2)
return true; //p1 and p2 met, so this means that there is a cycle
}
}
catch(NullPointerException npe)
{
//This means that p2 could not move forward
return false;
}
return false;
}