Explique cómo funciona el nodo de inicio del ciclo de búsqueda en la lista de ciclos vinculados.

Entiendo que la reunión de Tortuga y Liebre concluye la existencia del bucle, pero ¿cómo se mueve la tortuga al comienzo de la lista vinculada mientras se mantiene a la liebre en el lugar de reunión, seguido de mover ambos un paso a la vez para que se encuentren en el punto de inicio del ciclo?

Este es el algoritmo de Floyd para la detección de ciclos . Estás preguntando acerca de la segunda fase del algoritmo: una vez que hayas encontrado un nodo que es parte de un ciclo, ¿cómo se encuentra el inicio del ciclo?

En la primera parte del algoritmo de Floyd, la liebre mueve dos pasos por cada paso de la tortuga. Si la tortuga y la liebre alguna vez se encuentran, hay un ciclo, y el punto de encuentro es parte del ciclo, pero no necesariamente el primer nodo del ciclo.

Cuando la tortuga y la liebre se encuentran, hemos encontrado la i más pequeña (el número de pasos dados por la tortuga) tal que X _i = X _2i . Deje que mu represente el número de pasos para llegar de X ₀ al comienzo del ciclo, y deje que lambda represente la duración del ciclo. Entonces i = mu + a lambda, y 2i = mu + b lambda, donde a y b son enteros que indican cuántas veces la tortuga y la liebre dieron la vuelta al ciclo. Restando la primera ecuación de la segunda da i = (ba) * lambda, entonces yo es un múltiplo entero de lambda. Por lo tanto, X _{i + mu} = X _mu . X _i representa el punto de encuentro de la tortuga y la liebre. Si mueve la tortuga de regreso al nodo inicial X₀ , y deje que la tortuga y la liebre continúen a la misma velocidad, después de mu pasos adicionales, la tortuga habrá alcanzado X _mu , y la liebre habrá alcanzado X _{i + mu} = X _mu , por lo que el segundo punto de encuentro indica el inicio de la ciclo.

Permítanme intentar aclarar el algoritmo de detección de ciclo que se proporciona en http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare en mis propias palabras.

Cómo funciona

Tengamos una tortuga y una liebre (nombre de los punteros) que señalen el comienzo de la lista con un ciclo, como en el diagrama anterior.

Supongamos que si movemos la tortuga 1 paso a la vez, y tenemos 2 pasos a la vez, eventualmente se encontrarán en un punto. Demostremos que, en primer lugar, esta hipótesis es cierta.

La figura ilustra una lista con un ciclo. El ciclo tiene una duración de ne inicialmente estamos a unos mpasos del ciclo. También digamos que el punto de encuentro está a kpasos del comienzo del ciclo y la tortuga y la liebre se encuentran cuando la tortuga ha dado los ipasos totales. (Hare habría dado 2ipasos totales para entonces).

Las siguientes 2 condiciones deben cumplir:

1) i = m + p * n + k

2) 2i = m + q * n + k

El primero dice que la tortuga mueve ipasos y en estos ipasos primero llega al ciclo. Luego pasa por los ptiempos de ciclo para algún número positivo p. Finalmente, pasa por kmás nodos hasta que se encuentra con la liebre.

Un similar es cierto para la liebre. Mueve los 2ipasos y en estos 2ipasos primero llega al ciclo. Luego pasa por los qtiempos de ciclo para algún número positivo q. Finalmente, pasa por kmás nodos hasta que se encuentra con la tortuga.

Como la liebre viaja con el doble de velocidad que la tortuga, y el tiempo es constante para ambos cuando llegan al punto de encuentro.

Entonces, usando una relación simple de velocidad, tiempo y distancia,

2 ( m + p * n + k ) = m + q * n + k

=> 2m + 2pn + 2k = m + nq + k 

=>  m + k = ( q - 2p ) n

Entre m, n, k, p, q, los dos primeros son propiedades de la lista dada. Si podemos demostrar que hay al menos un conjunto de valores para k, q, p que hace que esta ecuación sea verdadera, mostramos que la hipótesis es correcta.

Uno de estos conjuntos de soluciones es el siguiente:

p = 0

q = m

k = m n - m

Podemos verificar que estos valores funcionen de la siguiente manera:

m + k = ( q - 2p ) n  

=> m + mn - m = ( m - 2*0) n

=> mn = mn.

Para este conjunto, ies

i = m + p n + k

=> m + 0 * n + mn - m = mn.

Por supuesto, deberías ver que esto no es necesariamente el más pequeño posible. En otras palabras, la tortuga y la liebre ya podrían haberse encontrado antes muchas veces. Sin embargo, como mostramos que se encuentran en algún momento al menos una vez, podemos decir que la hipótesis es correcta. Por lo tanto, tendrían que reunirse si movimos uno de ellos 1 paso, y el otro 2 pasos a la vez.

Ahora podemos pasar a la segunda parte del algoritmo, que es cómo encontrar el comienzo del ciclo.

Comienzo del ciclo

Una vez que la tortuga y la liebre se encuentran, volvamos a la tortuga al principio de la lista y mantengamos la liebre donde se encontraron (que está a k pasos del comienzo del ciclo).

La hipótesis es que si dejamos que se muevan a la misma velocidad (1 paso para ambos), la primera vez que se vuelvan a encontrar será el comienzo del ciclo.

Probemos esta hipótesis.

Primero supongamos que algún oráculo nos dice qué es m.

Luego, si dejamos que muevan m + k pasos, la tortuga tendría que llegar al punto en que se encontraron originalmente (k pasos lejos del comienzo del ciclo, ver en la figura).

Anteriormente mostramos eso m + k = (q - 2p) n.

Dado que m + k pasos es un múltiplo de la longitud del ciclo n, la liebre, en el tiempo medio, pasaría por el ciclo (q-2p) veces y volvería al mismo punto (k pasos lejos del comienzo del ciclo).

Ahora, en lugar de dejar que se muevan m + k pasos, si dejamos que se muevan solo m pasos, la tortuga llegaría al comienzo del ciclo. La liebre estaría a k pasos de completar (q-2p) rotaciones. Como comenzó k pasos delante del comienzo del ciclo, las liebres tendrían que llegar al comienzo del ciclo.

Como resultado, esto explica que tendrían que reunirse en el ciclo que comienza después de cierto número de pasos por primera vez (la primera vez porque la tortuga acaba de llegar al ciclo después de m pasos y nunca podría ver liebre que ya estaba en el ciclo).

Ahora sabemos que la cantidad de pasos que necesitamos para moverlos hasta que se encuentren resulta ser la distancia desde el comienzo de la lista hasta el comienzo del ciclo, m. Por supuesto, el algoritmo no necesita saber qué es m. Solo moverá la tortuga y la liebre paso a paso hasta que se encuentren. El punto de encuentro debe ser el inicio del ciclo y el número de pasos debe ser la distancia (m) al comienzo del ciclo. Suponiendo que conocemos la longitud de la lista, también podemos calcular la longitud del ciclo de restar m de la longitud de la lista.

Refiera esta imagen:

Distancia recorrida por slowPointer antes de la reunión = x + y

Distancia recorrida por el puntero rápido antes de la reunión = (x + y + z) + y = x + 2y + z

Dado que fastPointer viaja con el doble de velocidad que slowPointer, y el tiempo es constante para ambos cuando llegan al punto de encuentro.

Entonces, usando 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, moviendo slowPointer para comenzar la lista vinculada y haciendo que slowPointer y fastPointer muevan un nodo a la vez, ambos tienen la misma distancia que cubrir .

Llegarán al punto donde comienza el ciclo en la lista vinculada.

_{La respuesta simple y subestimada de Old Monk explica cómo encontrar el ciclo cuando el corredor rápido completa solo un ciclo completo. En esta respuesta, explico el caso cuando el corredor rápido ha ejecutado el ciclo varias veces antes de que el corredor lento entre en el ciclo.}

Usando la misma imagen:

Digamos que el corredor rápido ha corrido el bucle m veces antes de encontrarse lento y rápido. Esto significa que:

• Distancia recorrida por lento: x + y
• Distancia recorrida por rápido: x + m (y + z) + y es decir, extra y donde se encuentran

Dado que las carreras rápidas tienen el doble de velocidad que las lentas, y que han estado funcionando durante el mismo tiempo, implica que si duplicamos la distancia recorrida lentamente, obtenemos la distancia recorrida rápidamente. Así,

• 2 (x + y) = x + m (y + z) + y

Resolviendo para x da,

x = (m - 1) (y + z) + z

En un escenario real significaría, x = (m - 1) ejecuciones completas del bucle + una distancia adicional z .

Por lo tanto, si colocamos un puntero al comienzo de la lista y dejamos el otro en el punto de encuentro, moverlos a la misma velocidad dará como resultado que el puntero en bucle complete m - 1 carreras del bucle y luego se encuentre con el otro puntero justo al comienzo del bucle.

Es muy muy simple. Puedes pensar en términos de velocidad relativa. Si el conejo mueve dos nodos y la tortuga mueve un nodo, en relación con la tortuga el conejo mueve un nodo (suponga que la tortuga está en reposo). Entonces, si movemos un nodo en la lista enlazada circular, seguramente nos encontraremos en ese punto nuevamente.

Después de encontrar el punto conectado dentro de la lista enlazada circular, ahora el problema se reduce a encontrar el punto de intersección de dos problemas de la lista enlazada.

En el momento de la primera colisión, la tortuga se movió m + k pasos como se muestra arriba. La liebre se mueve dos veces más rápido que la tortuga, lo que significa que la liebre se movió 2 (m + k) pasos. De estos simples hechos podemos derivar el siguiente gráfico.

En este punto, volvemos a mover a la tortuga al inicio y declaramos que tanto la liebre como la tortuga deben moverse paso a paso. Por definición, después de m pasos, la tortuga estará al comienzo del ciclo. ¿Dónde estará la liebre?

La liebre también estará al comienzo del ciclo. Esto queda claro en el segundo gráfico: cuando la tortuga se movió de regreso al inicio, la liebre fue k pasos en su último ciclo. Después de m pasos, la liebre habrá completado otro ciclo y colisionado con la tortuga.

Acercarse:

Hay dos punteros:

• Un puntero lento que mueve un nodo a la vez.
• Un puntero rápido que mueve dos nodos a la vez.

Si los dos punteros se encuentran, demuestra que hay un bucle. Una vez que se hayan encontrado, uno de los nodos apuntará a la cabeza y luego ambos avanzarán un nodo a la vez. Se encontrarán al comienzo del ciclo.

Justificación: Cuando dos personas caminan por una pista circular, una de ellas al doble de la velocidad de la otra, ¿dónde se encuentran? Exactamente donde comenzaron.

Ahora, supongamos que el corredor rápido tiene una ventaja inicial de kpasos en una nvuelta. ¿Dónde se encontrarán? Exactamente en los n-kpasos. Cuando el corredor lento ha cubierto los (n-k)pasos, el corredor rápido habría cubierto los k+2(n-k)pasos. ( es decir, k+2n-2kpasos , es decir, 2n-kpasos ). es decir(n-k) pasos (el camino es circular y no nos preocupa el número de rondas después de las cuales se encuentran; solo nos interesa la posición en la que se encuentran).

Ahora, ¿cómo consiguió el corredor rápido la ventaja de los kpasos en primer lugar? Porque le tomó al corredor lento tantos pasos para llegar al inicio del ciclo. Entonces, el inicio del ciclo es k pasos desde el nodo principal.

Nota: El nodo donde se encontraron ambos punteros está a kpasos del inicio del ciclo (dentro del ciclo) y el nodo principal también está a kpasos del inicio del ciclo. Entonces, cuando tengamos el puntero avanzando a un ritmo igual de 1 paso desde estos nodos, se encontrarán al comienzo del ciclo.

Creo que es sencillo. Avíseme si alguna parte es ambigua.

Bien, supongamos que la liebre y la tortuga se encuentran en un punto que está a k pasos del comienzo del ciclo, el número de pasos antes de que comience el ciclo es mu y la duración del ciclo es L.

Así que ahora en el punto de encuentro ->

Distancia cubierta por la tortuga = mu + a * L + k - Ecuación 1

(Pasos para alcanzar el comienzo del ciclo + pasos para cubrir las iteraciones 'a' del ciclo + k pasos desde el inicio del ciclo) (donde a es una constante positiva)

Distancia recorrida por la liebre = mu + b * L + k - Ecuación 2

(Pasos para alcanzar el comienzo del ciclo + pasos para cubrir las iteraciones 'b' del ciclo + k pasos desde el inicio del ciclo) (donde b es una constante positiva yb> = a)

Entonces, la distancia adicional cubierta por la liebre es = Ecuación 2 - Ecuación 1 = (ba) * L

Tenga en cuenta que esta distancia también es igual a la distancia de la tortuga desde el punto de partida ya que la liebre se mueve 2 veces más rápido que la tortuga. Esto puede equipararse a 'mu + k', que también es la distancia del punto de encuentro desde el principio si no incluimos múltiples recorridos del ciclo.

Por lo tanto, mu + k = (ba) * L

Entonces, mis pasos desde este punto llevarían de regreso al comienzo del ciclo (ya que k pasos desde el comienzo del ciclo ya se han tomado para llegar al punto de encuentro). Esto podría suceder en el mismo ciclo o en cualquiera de los ciclos posteriores. Por lo tanto, ahora si movemos la tortuga al comienzo de la lista vinculada, tomará mu pasos para llegar al punto de inicio del ciclo y la liebre tomaría mu pasos para también alcanzar el comienzo del ciclo y así ambos se encontrarían en el punto de partida del ciclo.

PD Honestamente, tenía la misma pregunta que el póster original en mi mente y leí la primera respuesta, aclararon algunas cosas, pero no pude llegar al resultado final con claridad, así que intenté hacerlo a mi manera y Me resultó más fácil de entender.

credito de imagen

La distancia de la llamada al número de enlaces que sigue un puntero, y el tiempo al número de iteraciones que toma el algoritmo para mover el puntero lento un enlace y el puntero rápido dos enlaces. Hay N nodos antes de un ciclo de longitud C, etiquetados con desplazamiento de ciclo k = 0 a C-1.

Para alcanzar el inicio del ciclo, lento toma N tiempo y distancia. Esto significa que rápido toma N distancia en el ciclo (N para llegar allí, N para girar). Entonces, en el momento N, lento está en el desplazamiento del ciclo k = 0, y rápido está en el desplazamiento del ciclo k = N mod C.

Si N mod C es cero, lento y rápido ahora coinciden y el ciclo se encuentra en el momento N y la posición del ciclo k = 0.

Si N mod C no es cero, entonces rápido ahora tiene que ponerse al día con lento, que en el momento N es C- (N mod C) distancia atrás en el ciclo.

Dado que los movimientos rápidos 2 por cada 1 de lento, reduciendo la distancia en 1 en cada iteración, esto toma tanto tiempo adicional como la distancia entre rápido y lento en el tiempo N, que es C- (N mod C). Como lento se mueve desde el desplazamiento 0, este también es el desplazamiento donde se encuentran.

Entonces, si N mod C es cero, la fase 1 se detiene después de N iteraciones al comienzo del ciclo. De lo contrario, la fase 1 se detiene después de las iteraciones N + C- (N mod C) en el desplazamiento C- (N mod C) en el ciclo.

// C++ pseudocode, end() is one after last element.

int t = 0;
T *fast = begin();
T *slow = begin();
if (fast == end()) return [N=0,C=0];
for (;;) {
    t += 1;
    fast = next(fast);
    if (fast == end()) return [N=(2*t-1),C=0];
    fast = next(fast);
    if (fast == end()) return [N=(2*t),C=0];
    slow = next(slow);
    if (*fast == *slow) break;
}

Ok, entonces la fase 2: lento toma N más pasos para llegar al ciclo, en cuyo punto rápido (ahora moviéndose 1 por paso de tiempo) está en (C- (N mod C) + N) mod C = 0. Entonces se encuentran al comienzo del ciclo después de la fase 2.

int N = 0;
slow = begin();
for (;;) {
    if (*fast == *slow) break;
    fast = next(fast);
    slow = next(slow);
    N += 1;
}

Para completar, la fase 3 calcula la duración del ciclo moviéndose una vez más a través del ciclo:

int C = 0;
for (;;) {
    fast = next(fast);
    C += 1;
    if (fast == slow) break;
}

Reduzca el problema a un problema de bucle, luego regrese al problema inicial

Encuentro la siguiente explicación más intuitiva.

1. Tome dos punteros ( 1 = tortuga y 2 = liebre) que comienzan desde la cabeza ( O ), 1 tiene una longitud de paso de 1 , 2 tiene una longitud de paso de 2 . Piense en el momento en que 1 alcanza el nodo de inicio de ese ciclo ( A ).

   Queremos responder a la siguiente pregunta "¿Dónde está 2 cuando 1 está en A?".

   Entonces, OA = aes un número natural ( a >= 0). Pero se puede escribir de la siguiente manera:, a = k*n + bdonde a, k, n, b are natural numbers:

   • n = la duración del ciclo
   • k >= 0 = constante
   • 0 <= b <= n-1

   Esto significa que b = a % n.

   Por ejemplo: si a = 20y n = 8=> k = 2y b = 4porque 20 = 2*8 + 4.

   La distancia recorrida por 1 es d = OA = a = k*n + b. Pero al mismo tiempo, 2 cubiertas D = 2*d = d + d = OA + d = OA + k*n + b. Esto significa que cuando 2 está en A tiene que cubrirse k*n + b. Como se puede ver, kes el número de vueltas, pero después de esas vueltas, 2 será b lejos de A. Así, encontramos, donde 2 es cuando 1 se encuentra en la llamada de A. Let ese punto B, donde AB = b.

   

2. Ahora, reducimos el problema a un círculo. La pregunta es "¿Dónde está el punto de encuentro?" . ¿Dónde está esa C ?

   

   En cada paso, 2 reduce la distancia de 1 con 1(digamos metro) porque 1 se aleja de 2 con 1, pero al mismo tiempo 2 se acerca a 1 por 2.

   Entonces, la intersección será cuando la distancia entre 1 y 2 sea ​​cero. Esto significa que 2 reduce la n - bdistancia. Para lograr esto, 1 hará n - bpasos, mientras que 2 hará 2*(n - b)pasos.

   Entonces, el punto de intersección estará n - blejos de A (en el sentido de las agujas del reloj), porque esta es la distancia cubierta por 1 hasta que se encuentra con 2 . => la distancia entre C y A es CA = b, porque AC = AB + BC = n - by CA = n - AC. No piense que AC = CA, debido a que la ACdistancia no es una distancia matemática trivial, es el número de pasos entre A y C (donde A es el punto de inicio y C es el punto final).

3. Ahora, volvamos al esquema inicial.

   Lo sabemos a = k*n + by CA = b.

   Podemos tomar 2 punteros nuevos 1 ' y 1' ' , donde 1' comienza desde la cabeza ( O ) y 1 '' comienza desde el punto de intersección ( C ).

   Mientras 1 ' va de O a A , 1' ' va de C a A y continúa terminando kvueltas. Por lo tanto, el punto de intersección es una .

   

   

Si los punteros se encontraron en un punto P como se muestra en la figura, la distancia Z + Y es el punto P y X + Y también es el punto P, lo que significa Z = X. Es por eso que seguir moviendo un puntero desde P y moviendo otro desde el inicio (S) hasta que se encuentran, lo que significa mover una distancia igual (Z o X) al mismo punto M (distancia Z desde P y X desde S) será el inicio del ciclo. ¡Sencillo!

Con todo el análisis anterior, si usted es una persona que aprende con el ejemplo, traté de escribir un breve análisis y un ejemplo que ayude a explicar las matemáticas que todos los demás intentaron explicar. ¡Aquí vamos!

Análisis:

Si tenemos dos punteros, uno más rápido que el otro, y los movemos juntos, eventualmente se encontrarán nuevamente para indicar un ciclo o nulos para indicar que no hay ciclo.

Para encontrar el punto de partida del ciclo, dejemos ...

1. m ser la distancia desde la cabeza hasta el comienzo del ciclo;

2. d ser el número de nodos en el ciclo;

3. p1 ser la velocidad del puntero más lento;

4. p2ser la velocidad del puntero más rápido, por ejemplo. 2 significa pasos a través de dos nodos a la vez.

   Observe las siguientes iteraciones:

 m = 0, d = 10:
 p1 = 1:  0  1  2  3  4  5  6  7  8  9 10 // 0 would the start of the cycle
 p2 = 2:  0  2  4  6  8 10 12 14 16 18 20

 m = 1, d = 10:
 p1 = 1: -1  0  1  2  3  4  5  6  7  8  9
 p2 = 2: -1  1  3  5  7  9 11 13 15 17 19

 m = 2, d = 10:
 p1 = 1: -2 -1  0  1  2  3  4  5  6  7  8
 p2 = 2: -2  0  2  4  6  8 10 12 14 16 18

A partir de los datos de muestra anteriores, podemos descubrir fácilmente que cada vez que se encuentran los punteros más rápidos y más lentos, están a unos mpasos del comienzo del ciclo. Para resolver esto, vuelva a colocar el puntero más rápido en la cabeza y ajuste su velocidad a la velocidad del puntero más lento. Cuando se vuelven a encontrar, el nodo es el comienzo del ciclo.

digamos,

N[0] is the node of start of the loop, 
m is the number of steps from beginning to N[0].

Tenemos 2 punteros A y B, A corre a velocidad 1x, B a velocidad 2x, ambos comienzan desde el principio.

cuando A alcanza N [0], B ya debería estar en N [m]. (Nota: A usa m pasos para alcanzar N [0], y B debe estar m pasos más adelante)

Luego, A ejecuta k más pasos para colisionar con B, es decir, A está en N [k], B está en N [m + 2k] (Nota: B debe ejecutar 2k pasos a partir de N [m])

A colisionan B en N [k] y N [m + 2k] respectivamente, significa k = m + 2k, por lo tanto k = -m

Por lo tanto, para volver al N [0] desde N [k], necesitamos m más pasos.

Simplemente diciendo, solo necesitamos ejecutar m pasos más después de encontrar el nodo de colisión. Podemos tener un puntero para ejecutar desde el principio y un puntero desde el nodo de colisión, se encontrarán en N [0] después de m pasos.

Por lo tanto, los pseudocódigos son los siguientes:

1) A increase 1 step per loop
2) B increase 2 steps per loop
3) if A & B are the same node, cycle found, then go to 5
4) repeat from 1
5) A reset to head
6) A increase 1 step per loop
7) B increase 1 step per loop
8) if A & B are the same node, start of the cycle found
9) repeat from 6

No creo que sea cierto que cuando se encuentran ese es el punto de partida. Pero sí, si el otro puntero (F) estaba en el punto de encuentro antes, entonces 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 lo hará terminar al comienzo del ciclo. por ejemplo:

1->2->3->4->5->6->7->8->9->10->11->12->13->14->15->16->17->18->19->20->21->22->23->24->8

Meet at :16

Start at :8

public Node meetNodeInLoop(){

    Node fast=head;
    Node slow=head;

    fast=fast.next.next;
    slow=slow.next;

    while(fast!=slow){

        fast=fast.next;
        fast=fast.next;

        if(fast==slow) break; 

        slow=slow.next;
    }

    return fast;

}

public Node startOfLoop(Node meet){

    Node slow=head;
    Node fast=meet;

    while(slow!=fast){
        fast=fast.next;
        if(slow==fast.next) break;
        slow=slow.next;
    }

    return slow;
}

Una explicación simple que utiliza la idea de la velocidad relativa que se enseña en la escuela secundaria: conferencias de física 101 / cinemática.

1. Supongamos que la distancia desde el inicio de la lista vinculada hasta el inicio del círculo es xsaltos. Llamemos al inicio del círculo como punto X(en mayúsculas; consulte la figura anterior). También supongamos que el tamaño total del círculo es N saltos.

2. Velocidad de liebre = 2 * Velocidad de tortuga. Entonces eso es 1 hops/secy 2 hops/secrespectivamente

3. Cuando la tortuga alcanza el comienzo del círculo X, la liebre debe estar más xlejos en el punto Yde la figura. (Porque la liebre ha recorrido el doble de distancia que la tortuga).

4. Por lo tanto, la longitud del arco restante en el sentido de las agujas del reloj de X a Y sería N-x. Esto también es la distancia relativa a cubrir entre la liebre y la tortuga para que puedan encontrarse . Digamos que esta distancia relativa se cubrirá en el tiempo, t_mes decir, el tiempo para encontrarse. La velocidad relativa es (2 hops/sec - 1 hops/sec)ie 1 hops/sec. Así, usando, distancia relativa = velocidad relativa X tiempo, obtenemos, t= N-xseg. Por lo tanto, se necesitará N-xllegar al punto de encuentro tanto para la tortuga como para la liebre.

5. Ahora en N-xsegundos y a gran 1 hops/secvelocidad, la tortuga que estaba antes en el punto Xcubrirá los saltos de Nx para llegar al punto de encuentro M. Entonces, eso significa que el punto de encuentro Mestá en el N-xlúpulo en sentido antihorario desde X= (lo que implica además) => que hay una xdistancia restante desde el punto Mhacia la Xderecha.

6. Pero xtambién es la distancia para llegar al punto Xdesde el inicio de la lista vinculada.

7. Ahora, no nos importa a qué número de saltos xcorresponde. Si colocamos una tortuga al comienzo de LinkedList y una tortuga en el punto de encuentro My les dejamos saltar / caminar, entonces se encontrarán en el punto X, que es el punto (o nodo) que necesitamos.

Trabajar esto con un diagrama ayudaría. Estoy tratando de explicar el problema sin ecuaciones.

1. Si dejamos que la liebre y la tortuga corran en círculo y la liebre corre dos veces, entonces, al final de una vuelta para la tortuga liebre sería a la mitad. Al final de dos vueltas de la tortuga liebre habría hecho 1 vuelta y ambos se encuentran. Esto se aplica a toda la velocidad, como si la liebre corre tres veces, la liebre 1 vuelta es igual a 1/3 de la tortuga, por lo que al final de 3 vueltas para la liebre la tortuga habría cubierto 1 vuelta y se encuentran.
2. Ahora, si los comenzamos m pasos antes del bucle, significa que la liebre más rápida está comenzando en bucle. Entonces, si la tortuga alcanza el inicio del bucle, la liebre está m pasos adelante del bucle y cuando se encuentran, serían m pasos antes del inicio del bucle.

-hay k pasos antes del bucle. No sabemos qué es k y no necesitamos averiguarlo. Podemos trabajar de manera abstracta con solo k.

--Después de k pasos

----- T está al comienzo del ciclo

----- H son k pasos en el ciclo (pasó 2k en total y por lo tanto k en bucle)

** ahora son de tamaño de bucle, separados por k

(tenga en cuenta que k == K == mod (loopsize, k) --eg si un nodo tiene 2 pasos en un ciclo de 5 nodos, también tiene 7, 12 o 392 pasos, entonces, ¿qué tan grande es el ciclo wrt k no? factor en.

Dado que se alcanzan el uno al otro a razón de 1 paso por unidad de tiempo porque uno se mueve dos veces más rápido que el otro, se encontrarán a loopsize - k.

Esto significa que tomará k nodos para alcanzar el comienzo del ciclo y, por lo tanto, la distancia desde la cabeza hasta el inicio del ciclo y la colisión al inicio del ciclo son las mismas.

Así que ahora, después de la primera colisión, mueve T de nuevo a la cabeza. T y H se encontrarán al inicio del ciclo si te mueves a una velocidad de 1 cada uno. (en k pasos para ambos)

Esto significa que el algoritmo es:

• desde la cabeza mueva T = t.next y H.next.next hasta que choquen (T == H) (hay un ciclo)

// tenga cuidado con el caso cuando k = 0 o T y H se encuentran en la parte superior del bucle calculando la longitud del bucle

- cuente la duración del ciclo moviendo T o H a su alrededor con un contador

- mueva un puntero T2 al encabezado de la lista

- mover la longitud del puntero de los pasos del ciclo

- mueva otro puntero H2 a la cabeza

- mueva T2 y H2 en tándem hasta que se encuentren al inicio del ciclo

¡Eso es!

Ya hay muchas respuestas a esto, pero una vez se me ocurrió un diagrama para esto que es más intuitivo para mí. Quizás pueda ayudar a otras personas.

Los principales momentos aha para mí fueron:

• Dividir T (tortuga) en T1 (pre-loop) y T2 (in-loop).

• Resta T de H , donde se superponen visualmente. Lo que queda ( H - T = h' ) es igual a T .

• Las matemáticas restantes son bastante simples.

Sé que ya hay una respuesta aceptada para este problema, pero aún intentaré responder de manera fluida. Asumir:

The length of the Path is 'X+B' where 'B' is the length of the looped path and X of the non looped path. 
    Speed of tortoise : v
    Speed of hare     : 2*v 
    Point where both meet is at a distance 'x + b - k' from the starting point.

Ahora, que la liebre y la tortuga se encuentren después del tiempo 't' desde el principio.

Observaciones:

Si, Distancia recorrida por la tortuga = v * t = x + (bk) (decir)

Entonces, Distancia recorrida por la liebre = 2 * v * t = x + (b - k) + b (ya que la liebre ya ha atravesado la parte en bucle)

Ahora, los horarios de las reuniones son los mismos.

=> x + 2 * b - k = 2 * (x + b - k)

=> x = k

Por supuesto, esto significa que la longitud de la ruta que no está en bucle es la misma que la distancia del punto de inicio del bucle desde el punto donde ambos se encuentran.

En realidad, es fácil demostrar que ambos se encontrarán en el punto de partida, si considera las matemáticas detrás del punto de encuentro.
Primero, denote m el punto de inicio del ciclo en la lista vinculada, yn denota la duración del ciclo. Luego, para que la liebre y la tortuga se encuentren, tenemos:

( 2*t - m )%n = (t - m) %n, where t = time (at t = 0 , both are at the start)

Dicho esto más matemáticamente:

(2*t - m - (t - m) ) = 0 modulo n , which implies , t = 0 modulo n 

entonces se encontrarán en el tiempo t, que debería ser un múltiplo de la duración del ciclo. Esto significa que se encuentran en un lugar, que es (t-m) modulo n = (0-m) modulo n = (-m) modulo n.

Entonces, volviendo a la pregunta, si mueve un puntero desde el inicio de la lista vinculada y otro desde el punto de intersección, después de m pasos, la liebre (que se mueve dentro del ciclo) llegará a un punto que es ((-m) + m) modulo n = 0 modulo nque no es más que el punto de partida del ciclo. Entonces podemos ver que después de m pasos llega al comienzo del ciclo y la tortuga lo encontrará allí, ya que atravesará m pasos desde el comienzo de la lista vinculada.

Como nota al margen, también podemos calcular el tiempo de su intersección de esta manera: la condición t = 0 modulo nnos dice que se encontrarán en un momento que es un múltiplo de la duración del ciclo, y también t debería ser mayor que m como se encontrarían en el ciclo . Por lo tanto, el tiempo necesario será igual al primer múltiplo de n, que es mayor que m .

Suponga que sus punteros se encuentran en la intersección de los puntos y y z.

nym son los números de bucles que toma el puntero más rápido y más lento, respectivamente, antes de reunirse.

Consulte la imagen para el resto de la prueba. Encuentre el punto de inicio del bucle en la lista vinculada