El algoritmo para determinar si una única lista enlazada tiene un ciclo requiere al menos varios punteros
q, donde p avanza un paso cada vez y q avanza dos pasos cada vez.
La pregunta principal que debemos entender aquí es ¿por qué pyq tienen que coincidir cuando hay un anillo en una lista enlazada individualmente?
Supongamos que la longitud de la lista enlazada individualmente es n, y que la lista enlazada individualmente es circular, luego, en la iteración i-ésima, p apunta al elemento i
mod
n y q apunta al elemento 2i
mod
n. Por lo tanto, p y q se encuentran cuando i ≡ 2i (mod
n). Y i ≡ 2i(mod
n)
=>
(2i
-
i)
mod
n
=
=>
i
mod
n
=
=>
Cuando i=n, p y q se encuentran. El entendimiento simple es que p y q están corriendo en el patio de recreo al mismo tiempo, y la velocidad de q es el doble que la de p. Cuando empiezan a correr al mismo tiempo, p corre una vuelta para llegar al punto de partida, mientras que q acaba de correr dos vueltas para llegar al punto de partida.
Entonces, ¿qué sucede si p y q parten de puntos de partida diferentes? Supongamos que en la i-ésima iteración, p apunta al elemento i
mod
n y q apunta a k+2i
mod
. n, donde 0 n) => (i+k) mod => p> n = => P intersecta a q cuando i= n-k. Solución: Generalización: 1. Si las velocidades de los dos punteros son diferentes, como p y q, ( 0 Sp(i) = pi Sq(i) = k + qi Si los dos se cruzan con un nodo, entonces Sp(i) = Sq(i) => (pi) mod n = ( k+ qi ) mod n =>[ (q -p) i + k ] mod n =0 => p> (q-p)i + k = Nn [N es un número natural) =>p> i = (Nn -k) /(p-q) i toma un número natural, entonces cuando p y q satisfacen la fórmula anterior , Es decir: Existe un número natural N. Cuando es múltiplo de - q, puede satisfacer Nn -k Intersección garantizada. Caso especial: Si el tamaño del paso de q es el doble que el de p , y ambos parten del mismo punto de partida, es decir, q = 2p , k =0, Entonces la ecuación queda: Nn=i: Es decir, se puede entender que cuando i es un múltiplo entero del círculo en el i En la iteración, los dos pueden cruzarse y el punto de intersección es el punto de partida. 2. ¿Cómo determinar la longitud del anillo de una única lista enlazada? Esto es relativamente sencillo, sólo debes saber que q ha entrado al ring y guarda la posición. Luego, atravesamos el anillo a partir de esta posición, y cuando volvemos a encontrar la posición q , el número de veces que atravesamos es la longitud del anillo. 3. ¿Cómo encontrar el primer nodo del anillo en la lista enlazada? Supongamos que la longitud de la lista enlazada es L, la longitud de la primera mitad es k-1, luego el primer nodo que ingresa nuevamente al anillo es k y la longitud del anillo es n, entonces Cuando q = 2p, ¿cuándo es la primera intersección? Cuando el puntero q apunta al k-ésimo nodo, el puntero q ya está en el k mod n posición del anillo. En otras palabras, p y q difieren en k elementos y comienzan desde diferentes puntos de partida, entonces la posición de la intersección es n-k Es obvio Se puede ver en la figura que cuando p atraviesa k nodos hacia adelante desde el punto de intersección (n-k) , alcanza los primeros puntos del anillo, es decir, la posición del nodo k. Entonces el algoritmo es muy simple: Un puntero proviene de la primera intersección de p y q , en la posición que comienza en (n-k), y el otro puntero A proviene del encabezado del recorrido de la lista vinculada y su punto de intersección es el primer punto de intersección de la lista vinculada en el anillo. 4. ¿Qué pasa si se determina que dos listas enlazadas individualmente se cruzan? ¿Dónde está la primera intersección? Esta pregunta se puede transformar fácilmente en la pregunta anterior haciendo un dibujo. Al conectar el nodo de cola y el nodo principal de una de las listas vinculadas, es fácil ver que este problema se ha transformado en la pregunta 3, que es encontrar el primer nodo en el anillo de la lista vinculada. con un anillo.