algorithm - resultados - Explique cómo funciona la búsqueda de un nodo de inicio de ciclo en la lista de enlaces cíclicos.

resultados de busqueda de google (17)

Entiendo que la reunión de Tortoise and Hare concluye la existencia de loop, pero ¿cómo se mueve la tortuga al principio de la lista enlazada mientras se mantiene la liebre en el lugar de reunión, y luego se mueven paso a paso para que se encuentren en el punto de partida del ciclo?

Con todo el análisis anterior, si usted es una persona que aprende por ejemplo, intenté escribir un breve análisis y un ejemplo que ayuda 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 de nuevo para indicar un ciclo o nulo para indicar que no hay ciclo.

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

m sea la distancia desde la cabeza hasta el comienzo del ciclo;
d sea la cantidad de nodos en el ciclo;
p1 sea la velocidad del puntero más lento;
p2 sea la velocidad del puntero más rápido, ej. 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 los punteros más rápidos y lentos se encuentran, están a unos pasos del inicio del ciclo. Para resolver esto, coloque el puntero más rápido hacia atrás en la cabeza y establezca su velocidad a la velocidad del puntero más lento. Cuando se encuentran nuevamente, el nodo es el comienzo del ciclo.

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

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

Afirmando esto más matemáticamente:

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

para que se reúnan en el tiempo t, que debe ser un múltiplo de la duración del ciclo. Esto significa que se encuentran en una ubicación, que es (tm) modulo n = (0-m) modulo n = (-m) modulo n .

Entonces, volviendo a la pregunta, si mueves un puntero desde el inicio de la lista enlazada, y otro desde el punto de intersección, después de m pasos, tendremos la liebre (que se mueve dentro del ciclo) llegar a un punto que es ((-m) + m) modulo n = 0 modulo n que no es más que el punto de partida del ciclo. Así que 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 inicio de la lista enlazada.

Como nota al margen, también podemos calcular el tiempo de su intersección de esta manera: la condición t = 0 modulo n nos 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. Entonces el tiempo tomado será igual al primer múltiplo de n que sea mayor que m .

Es muy muy simple. Puedes pensar en términos de velocidad relativa en la cinemática de la física. Si el conejo se mueve dos nodos y la tortuga se mueve un nodo, en relación con el conejo tortuga se mueve un nodo (suponiendo que la tortuga está en reposo). Entonces, si movemos un nodo en la lista de enlaces circulares, seguramente nos encontraremos en ese punto nuevamente.

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

Está bien, supongamos que la liebre y la tortuga se encuentran en un punto que está a unos 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.

Entonces ahora en el punto de encuentro ->

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

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

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

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

Entonces la distancia extra 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 se puede equiparar a ''mu + k'', que también es la distancia del punto de reunión desde el principio si no incluimos múltiples recorridos del ciclo.

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

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

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

Este es el algoritmo de Floyd para la detección de ciclos . Estás preguntando sobre la segunda fase del algoritmo: una vez que has 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 para cada paso de la tortuga. Si la tortuga y la liebre se encuentran, existe 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 el menor i (el número de pasos tomados por la tortuga) de modo que X _i = X _2i . Deje que mu represente el número de pasos para obtener desde X ₀ hasta el 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 números enteros que indican cuántas veces la tortuga y la liebre rodearon el ciclo. Restar la primera ecuación del segundo da i = (ba) * lambda, entonces i 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 vuelta al nodo inicial X ₀ , y deja 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 , entonces el segundo punto de reunión denota el inicio del ciclo.

Hay un error en la mayoría de las soluciones para este problema. ¿Qué pasaría si el último nodo estuviera conectado al primero y fuera simplemente un bucle? ¿Qué pasaría si la velocidad lenta y rápida se encontrara a la cabeza del circuito la primera vez? No encontrarías la respuesta correcta con esa solución. Hay una respuesta correcta sobre cómo evitar esta situación, pero dado el camino feliz, con una cantidad de nodos k antes del ciclo, aquí hay una explicación simple: (si quieres saber más sobre la solución real, generalizada, ping yo)

-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á en el comienzo del ciclo

----- H es k pasos en el ciclo (obtuvo 2k en total y, por lo tanto, k en bucle)

** ahora están loopsize - k aparte

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

Como se alcanzan entre sí 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 en loopsize - k.

Esto significa que tomará k nodos para llegar al comienzo del ciclo y, por lo tanto, la distancia desde la cabeza al inicio del ciclo y la colisión al inicio del ciclo es la misma.

Entonces, después de la primera colisión, mueva T a la cabeza. T y H se encontrarán en cyclestart 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 colisionen (T == H) (hay un ciclo)

// cuidamos el caso cuando k = 0 o T y H se encontraron en la parte superior del ciclo calculando la longitud del ciclo

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

--move un puntero T2 a la cabeza de la lista

--move la duración del puntero de los pasos del ciclo

- mover otro puntero H2 a la cabeza

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

¡Eso es!

No creo que sea verdad que cuando se encuentran es el punto de partida. Pero sí, si el otro puntero (F) estaba en el punto de reunión anterior, entonces ese puntero estará al final del ciclo en lugar del inicio del ciclo y el puntero (S) que comenzó desde el inicio de la lista lo hará terminar al inicio 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; }

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.

Me refiero a la figura en mi explicación

Cómo funciona

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

Supongamos que si movemos tortuga paso por paso, y si hacemos 2 pasos a la vez, eventualmente se encontrarán en un punto. Demostremos que antes que nada esta hipótesis es verdadera.

La figura ilustra una lista con un ciclo. El ciclo tiene una longitud de n estamos inicialmente a unos pasos del ciclo. También digamos que el punto de encuentro está a unos pasos del comienzo del ciclo y la tortuga y la liebre se reúnen después de un total de i pasos.

Las siguientes 2 condiciones deben ser válidas:

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

El primero dice que la tortuga mueve i pasos y en estos i pasos primero llega al ciclo. Luego pasa por el ciclo p veces para un número positivo p . Finalmente pasa k más nodos hasta que se encuentra con la liebre.

Un similar es cierto para la liebre. Se mueve 2i pasos y en estos 2i pasos primero llega al ciclo. Luego pasa por el ciclo q veces para un número positivo q . Finalmente pasa k más nodos hasta que se encuentra con la tortuga.

Por lo tanto,

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, las dos primeras son propiedades de la lista dada. Si podemos demostrar que hay al menos un conjunto de valores para k, q, p que hacen 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 funcionan de la siguiente manera:

m + k = ( q - 2p ) n => m + mn - m = ( m - 2*0) n => mn = mn.

Para este conjunto, i

i = m + p n + k => m + 0 * n + mn - m = mn.

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

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

Ciclo de inicio

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

La hipótesis es que si les permitimos moverse a la misma velocidad (1 paso para ambos), la primera vez que se reúnan será el comienzo del ciclo.

Vamos a probar esta hipótesis.

Supongamos primero que algún oráculo nos dice qué es m.

Entonces, si les permitimos mover m + k pasos, la tortuga tendría que llegar al punto en el que se encontraron originalmente (k pasos más allá del comienzo del ciclo - ver en la figura).

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

Como m + k steps es un múltiplo de la longitud del ciclo n, liebre, mientras tanto, pasaría por el ciclo (q-2p) veces y volvería al mismo punto (k pasos más allá del comienzo del ciclo).

Ahora, en lugar de dejarlos mover m + k pasos, si les dejamos mover solo m pasos, la tortuga llegaría al comienzo del ciclo. Hare iría a ser k pasos cortos para completar rotaciones (q-2p). Como comenzó con k pasos antes del inicio del ciclo, la liebre debería llegar al comienzo del ciclo.

Como resultado, esto explica que tendrían que encontrarse en el ciclo que comienza después de una serie 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 la liebre que ya estaba en el ciclo).

Ahora sabemos que la cantidad de pasos que necesitamos para moverlos hasta que se encuentran 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. Simplemente moverá la tortuga y la liebre un paso a la vez 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 duración del ciclo de restar m de la longitud de la lista.

Refiere esta imagen:

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

Distancia recorrida por fastPointer antes de 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, al usar velocidad simple, relación de tiempo y distancia 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z

Por lo tanto, moviendo slowPointer al inicio de la lista enlazada, y haciendo que tanto slowPointer como fastPointer se muevan un nodo a la vez, ambos tienen la misma distancia que cubrir .

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

Sé que ya hay una respuesta aceptada para este problema, pero aún así 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, deja que la liebre y la tortuga se encuentren después del tiempo ''t'' desde el comienzo.

Observaciones:

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

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

Ahora, los tiempos de reunión son los mismos.

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

=> x = k

Esto, por supuesto, 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.

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

Si dejamos que la liebre y la tortuga corran en círculo y la liebre corra dos veces la tortuga, al final de una vuelta la liebre estaría a la mitad. Al final de las dos vueltas de la tortuga liebre habrían hecho 1 vuelta y ambos se encontrarán. Esto se aplica a toda velocidad, como si la liebre se ejecuta tres veces, liebre 1 vuelta equivale a 1/3 de la tortuga, por lo que al final de las 3 vueltas, la liebre habría cubierto una vuelta y se encontrarían.
Ahora si los iniciamos en m pasos antes del bucle, significa que la liebre más rápida está comenzando en un bucle. Por lo tanto, si la tortuga llega al inicio del ciclo, la liebre tiene un ciclo de m pasos por delante y cuando lo encuentre, habrá m pasos antes de que comience el ciclo.

Una explicación simple usando la idea de la velocidad relativa que se enseña en la escuela secundaria: clases de Física 101 / Cinemática.

Supongamos que la distancia desde el inicio de la lista vinculada al inicio del círculo es x saltos. Llamemos al comienzo del círculo como el punto X (en mayúsculas, vea la figura anterior). Supongamos también que el tamaño total del círculo es N saltos.
Velocidad de liebre = 2 * Velocidad de la tortuga. Entonces eso es 1 hops/sec y 2 hops/sec respectivamente
Cuando la tortuga alcanza el inicio del círculo X , la liebre debe estar aún x saltos en el punto Y de la figura. (Porque la liebre ha recorrido el doble de distancia que la tortuga).
Por lo tanto, la longitud del arco restante en el sentido de las agujas del reloj de X a Y sería Nx . También es la distancia relativa que debe cubrirse entre la liebre y la tortuga para poder encontrarse . Digamos que esta distancia relativa se cubrirá en el tiempo t_m es decir, la hora de la reunión. La velocidad relativa es (2 hops/sec - 1 hops/sec) es decir, 1 hops/sec . Por lo tanto, usando, distancia relativa = velocidad relativa X tiempo, obtenemos, t = Nx seg. Por lo tanto, Nx tardará en llegar al punto de encuentro tanto para la tortuga como para la liebre.
Ahora, en el tiempo de Nx sec y a la velocidad de 1 hops/sec , la tortuga que estaba antes en el punto X cubrirá Nx saltos para alcanzar el punto de encuentro M Entonces, eso significa que el punto de encuentro M está en Nx saltos en sentido antihorario desde X = (lo que implica más) => que hay x distancia restante del punto M a X sentido de las agujas del reloj.
Pero x es también la distancia para llegar al punto X desde el inicio de la lista vinculada.
Ahora, no nos importa a qué cantidad de saltos corresponde x . Si colocamos una tortuga al inicio de la LinkedList y una tortuga en el punto de encuentro M y las dejamos saltar / caminar, se encontrarán en el punto X , que es el punto (o nodo) que necesitamos.

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 una velocidad de 1x, B a una velocidad de 2x, ambos comienzan al principio.

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

Entonces, 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 ejecutarse durante 2k pasos comenzando desde N [m])

Una colisión 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 más pasos después de encontrar el nodo de colisión. Podemos tener un puntero para ejecutar desde el principio y un puntero que se ejecuta desde el nodo de colisión, se encontrarán en N [0] después de m pasos.

Por lo tanto, el pseudo código es el siguiente:

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

Enfoque:

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, prueba que hay un ciclo. Una vez que se hayan encontrado, uno de los nodos apuntará a la cabeza y luego ambos procederán de 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 velocidad que la otra, ¿dónde se encuentran? Exactamente donde comenzaron.

Ahora, supongamos que el corredor rápido tiene una ventaja inicial de k pasos en una vuelta n paso. ¿Dónde se encontrarán? Exactamente en nk pasos. Cuando el corredor lento ha cubierto (nk) pasos, el corredor rápido hubiera cubierto k+2(nk) pasos. ( es decir, k+2n-2k pasos, es decir, 2n-k pasos ). es decir, (nk) pasos (La ruta es circular y no estamos preocupados por la cantidad de rondas con las que se encuentran; solo nos interesa la posición en la que se encuentran).

Ahora, ¿cómo fue que el corredor rápido tuvo la ventaja inicial de k pasos en primer lugar? Porque le tomó al corredor lento muchos pasos para llegar al inicio del ciclo. Entonces, el comienzo del ciclo es k pasos desde el nodo principal.

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

Yo creo que es sencillo. Por favor, avíseme si alguna parte es ambigua.

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

Encuentro la siguiente explicación más intuitiva.

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 . Piensa en el momento en que 1 llega al nodo de inicio de ese ciclo ( A ).
Queremos responder a la siguiente pregunta "¿Dónde está 2 cuando 1 está en A?" .
Entonces, OA = a es un número natural ( a >= 0 ). Pero puede escribirse de la siguiente manera: a = k*n + b , donde a, k, n, b are natural numbers :
- n = la duración del ciclo
- k >= 0 = constante
- 0 <= b <= n-1
Significa que b = a % n .
Por ejemplo: si a = 20 n = 8 => k = 2 b = 4 porque 20 = 2*8 + 4 .
La distancia cubierta por 1 es d = OA = a = k*n + b . Pero al mismo tiempo, 2 cubren D = 2*d = d + d = OA + d = OA + k*n + b . Esto significa que cuando 2 está en A tiene que cubrir k*n + b . Como puede ver, k es el número de vueltas, pero después de esas vueltas, 2 estará b lejos de A. Entonces, encontramos dónde 2 es cuando 1 está en A. Llamemos a ese punto B , donde AB = b .
Ahora, reducimos el problema a un círculo. La pregunta es "¿Dónde está el punto de encuentro?" . ¿Dónde está ese C ?

En cada paso, 2 reduce la distancia de 1 a 1 (digamos medidor) porque 1 va más allá de 2 con 1 , pero al mismo tiempo 2 se acerca más a 1 por 2 .
Entonces, la intersección será cuando la distancia entre 1 y 2 sea cero. Esto significa que 2 reduce la distancia n - b . Para lograr esto, 1 hará n - b pasos, mientras que 2 harán 2*(n - b) pasos.
Entonces, el punto de intersección estará n - b lejos de A (en el sentido de las agujas del reloj), porque esta es la distancia cubierta por 1 hasta que se encuentre con 2 . => la distancia entre C y A es CA = b , porque AC = AB + BC = n - b y CA = n - AC . No piense que AC = CA , porque la distancia AC no es una distancia matemática trivial, es el número de pasos entre A y C (donde A es el punto inicial y C es el punto final).
Ahora regresemos al esquema inicial.
Sabemos que a = k*n + b y CA = b .
Podemos tomar 2 nuevos punteros de 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 completando k vueltas. Entonces, el punto de intersección es A.

_{La respuesta simple y subvitada 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 circuito varias veces antes de que el corredor lento ingrese al circuito.}

Usando la misma imagen:

Digamos que el corredor rápido ha corrido el lazo 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

Como las carreras rápidas con el doble de velocidad que las lentas, y que han estado funcionando por el mismo tiempo, implican que si duplicamos la distancia que corrimos por la velocidad lenta, 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 que x = (m - 1) bucle completo se ejecuta + una distancia adicional z .

Por lo tanto, si ponemos un puntero al principio de la lista y dejamos el otro en el punto de reunión, moverlos por la misma velocidad dará como resultado que el puntero de bucle completo complete m - 1 ejecuciones del ciclo y luego se encuentre con el otro puntero justo al comienzo del ciclo.

En el momento de la primera colisión, la tortuga 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 ha movido 2 (m + k) pasos. A partir de estos hechos simples, podemos derivar el siguiente gráfico.

En este punto, movemos tortuga de regreso 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á Hare?

Hare también estará al comienzo del ciclo. Esto es claro en el segundo gráfico: cuando la tortuga se movió de nuevo al comienzo, liebre estaba k pasos en su último ciclo. Después de m pasos, la liebre habrá completado otro ciclo y colisionó con la tortuga.