Explique como a localização do nó de início do ciclo na lista vinculada ao ciclo funciona?

Entendo que a reunião de Tartaruga e Hare conclui a existência de loop, mas como mover a tartaruga para o início da lista vinculada enquanto mantém a lebre no local da reunião, seguida de uma etapa de cada vez, faz com que elas se encontrem no ponto inicial do ciclo?

Este é o algoritmo de Floyd para detecção de ciclo . Você está perguntando sobre a segunda fase do algoritmo - depois de encontrar um nó que faz parte de um ciclo, como encontrar o início do ciclo?

Na primeira parte do algoritmo de Floyd, a lebre dá dois passos para cada passo da tartaruga. Se a tartaruga e a lebre se encontrarem, há um ciclo, e o ponto de encontro faz parte do ciclo, mas não necessariamente o primeiro nó do ciclo.

Quando a tartaruga e se encontram lebre, nós encontramos o menor i (o número de passos dados pela tartaruga) tal que X _i = X _2i . Permita que mu represente o número de etapas que vão de X ₀ até o início do ciclo e permita que lambda represente a duração do ciclo. Então i = mu + a lambda e 2i = mu + b lambda, onde aeb são números inteiros que denotam quantas vezes a tartaruga e a lebre percorreram o ciclo. Subtrair a primeira equação da segunda fornece i = (ba) * lambda, então i é um múltiplo inteiro de lambda. Portanto, Xi _{+ mu} = X _mu . X _i representa o ponto de encontro da tartaruga e lebre. Se você mover a tartaruga de volta ao nó inicial X₀ e deixe a tartaruga e a lebre continuarem na mesma velocidade; após mu etapas adicionais, a tartaruga alcançará X _mu , e a lebre alcançará X _{i + mu} = X _mu , portanto, o segundo ponto de encontro indica o início do ciclo.

Deixe-me tentar esclarecer o algoritmo de detecção de ciclo fornecido em http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare em minhas próprias palavras.

Como funciona

Vamos ter uma tartaruga e uma lebre (nome dos ponteiros) apontando para o início da lista com um ciclo, como no diagrama acima.

Vamos supor que, se movermos a tartaruga 1 passo de cada vez e dermos 2 passos por vez, eles acabarão se encontrando em um ponto. Vamos mostrar que, em primeiro lugar, essa hipótese é verdadeira.

A figura ilustra uma lista com um ciclo. O ciclo tem uma duração de ne estamos inicialmente a alguns mpassos do ciclo. Digamos também que o ponto de encontro está a alguns kpassos do início do ciclo e a tartaruga e a lebre se encontram quando a tartaruga toma imedidas totais. (Hare já teria tomado todas 2ias medidas até então).

As 2 condições a seguir devem ser mantidas:

1) i = m + p * n + k

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

O primeiro diz que a tartaruga move ietapas e, nessas ietapas, chega primeiro ao ciclo. Depois, percorre os ptempos de ciclo para obter um número positivo p. Finalmente, ele passa por kmais nós até encontrar a lebre.

O mesmo vale para a lebre. Ele move 2ietapas e, nessas 2ietapas, chega primeiro ao ciclo. Depois, percorre os qtempos de ciclo para obter um número positivo q. Finalmente, ele passa por kmais nós até encontrar a tartaruga.

Como a lebre viaja com o dobro da velocidade da tartaruga, e o tempo é constante para ambos quando atingem o ponto de encontro.

Então, usando simples relação de velocidade, tempo e distância,

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, os dois primeiros são propriedades da lista fornecida. Se pudermos mostrar que há pelo menos um conjunto de valores para k, q, p que torna essa equação verdadeira, mostramos que a hipótese está correta.

Um desses conjuntos de soluções é o seguinte:

p = 0

q = m

k = m n - m

Podemos verificar se esses valores funcionam da seguinte maneira:

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.

Obviamente, você deve ver que isso não é necessariamente o menor possível. Em outras palavras, tartaruga e lebre podem já ter se encontrado antes muitas vezes. No entanto, como mostramos que eles se encontram em algum momento pelo menos uma vez, podemos dizer que a hipótese está correta. Então eles teriam que se encontrar se movermos um deles 1 passo, e o outro 2 passos por vez.

Agora podemos ir para a segunda parte do algoritmo, que é como encontrar o início do ciclo.

Início do ciclo

Quando a tartaruga e a lebre se encontrarem, vamos colocar a tartaruga de volta ao início da lista e manter a lebre onde eles se conheceram (que está a k passos do início do ciclo).

A hipótese é que, se permitirmos que eles se movam na mesma velocidade (1 passo para ambos), a primeira vez que eles se encontrarem novamente será o início do ciclo.

Vamos provar esta hipótese.

Vamos primeiro assumir que algum oráculo nos diz o que é m.

Então, se permitirmos que eles movam m + k passos, a tartaruga terá que chegar ao ponto que eles se encontraram originalmente (k se afasta do início do ciclo - veja na figura).

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

Como m + k passos é um múltiplo de duração do ciclo n, a lebre, nesse meio tempo, passaria pelos tempos do ciclo (q-2p) e retornaria ao mesmo ponto (k se afastaria do início do ciclo).

Agora, em vez de deixá-los mover m + k passos, se os deixássemos mover apenas m passos, a tartaruga chegaria ao início do ciclo. A lebre seria k passos antes de completar as rotações (q-2p). Desde que iniciou k etapas antes do início do ciclo, a lebre teria que chegar ao início do ciclo.

Como resultado, isso explica que eles teriam que se encontrar no início do ciclo após várias etapas pela primeira vez (primeira vez porque a tartaruga acabou de chegar ao ciclo após m etapas e ela nunca conseguia ver a lebre que já estava dentro). o ciclo).

Agora sabemos que o número de etapas necessárias para movê-las até que elas se encontrem acaba sendo a distância do início da lista ao início do ciclo, m. Obviamente, o algoritmo não precisa saber o que é m. Apenas moverá a tartaruga e a lebre um passo de cada vez até que se encontrem. O ponto de encontro deve ser o início do ciclo e o número de etapas deve ser a distância (m) do início do ciclo. Supondo que sabemos o comprimento da lista, também podemos calcular a duração do ciclo de subtração m do comprimento da lista.

Consulte esta imagem:

Distância percorrida pelo slowPointer antes da reunião = x + y

Distância percorrida pelo fastPointer antes da reunião = (x + y + z) + y = x + 2y + z

Como o fastPointer viaja com o dobro da velocidade do slowPointer, o tempo é constante para ambos quando atingem o ponto de encontro.

Portanto, usando a relação simples de velocidade, tempo e distância 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z

Portanto, movendo o slowPointer para o início da lista vinculada e fazendo o slowPointer e o fastPointer moverem um nó de cada vez, ambos têm a mesma distância a percorrer .

Eles chegarão no ponto em que o loop inicia na lista vinculada.

_{A resposta simples e insuficiente do Old Monk explica como encontrar o ciclo quando o corredor rápido completa apenas um ciclo completo. Nesta resposta, explico o caso em que o corredor rápido executou o loop várias vezes antes de o corredor lento entrar no loop.}

Usando a mesma imagem:

Digamos que o corredor rápido tenha executado o loop m vezes antes de se encontrar lenta e rapidamente. Isso significa que:

• Distância percorrida lentamente: x + y
• Distância percorrida rapidamente: x + m (y + z) + y, ou seja, y extra onde eles se encontram

Como as corridas rápidas com o dobro da velocidade do slow, e que eles estão rodando pelo mesmo tempo, isso implica que, se dobrarmos a distância percorrida lentamente, obteremos a distância percorrida rapidamente. Portanto,

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

Resolver para x dá,

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

No cenário real, isso significa que x = (m - 1) corre o loop completo + uma distância extra z .

Portanto, se colocarmos um ponteiro no início da lista e deixarmos o outro no ponto de encontro, movê-los na mesma velocidade resultará no ponteiro do loop in concluir m-1 execuções do loop e depois encontrar o outro ponteiro logo no início do loop.

É muito, muito simples. Você pode pensar em termos de velocidade relativa. Se o coelho move dois nós e a tartaruga move um nó, em relação ao coelho da tartaruga está movendo um nó (assuma a tartaruga em repouso). Portanto, se movermos um nó na lista vinculada circular, certamente iremos nos encontrar nesse ponto novamente.

Depois de encontrar o ponto conectado dentro da lista vinculada circular, agora o problema é reduzido para encontrar o ponto de interseção de dois problemas na lista vinculada.

No momento da primeira colisão, a tartaruga movia m + k passos como mostrado acima. A lebre se move duas vezes mais rápido que a tartaruga, o que significa que a lebre se moveu 2 (m + k) etapas. A partir desses fatos simples, podemos derivar o gráfico a seguir.

Nesse ponto, movemos a tartaruga de volta ao início e declaramos que a lebre e a tartaruga devem dar um passo de cada vez. Por definição, após m etapas, a tartaruga estará no início do ciclo. Onde estará a lebre?

A lebre também estará no início do ciclo. Isso fica claro no segundo gráfico: quando a tartaruga foi movida de volta ao início, a lebre foi k em seu último ciclo. Após m etapas, a lebre terá completado outro ciclo e colidido com a tartaruga.

Abordagem:

Existem dois ponteiros:

• Um ponteiro lento que move um nó de cada vez.
• Um ponteiro rápido que move dois nós de cada vez.

Se os dois ponteiros se encontrarem, isso prova que há um loop. Depois que eles se encontrarem, um dos nós apontará para a cabeça e, em seguida, os dois prosseguirão um nó por vez. Eles se encontrarão no início do ciclo.

Fundamentação: Quando duas pessoas caminham por uma pista circular, uma delas com o dobro da velocidade da outra, onde elas se encontram? Exatamente onde eles começaram.

Agora, suponha que o corredor rápido tenha uma vantagem inicial de ketapas em uma nvolta. onde eles se encontrarão? Exatamente nas n-ketapas. Quando o corredor lento cobriu (n-k)etapas, o corredor rápido teria coberto k+2(n-k)etapas. ( isto é, k+2n-2ketapas , 2n-ketapas ). ie(n-k) etapas (o caminho é circular e não estamos preocupados com o número de rodadas após o qual eles se encontram; estamos apenas interessados ​​na posição em que eles se encontram).

Agora, como o corredor rápido conseguiu o começo das ketapas em primeiro lugar? Porque o corredor lento levou muitos passos para chegar ao início do ciclo. Portanto, o início do loop está a k passos do nó principal.

Nota: O nó em que ambos os ponteiros se encontram fica a alguns kpassos do início do loop (dentro do loop) e o nó principal também está a alguns kpassos do início do loop. Portanto, quando temos o ponteiro avançando a um passo igual a 1 passo do bot desses nós, eles se encontrarão no início do loop.

Eu acredito que é simples. Informe-me se alguma parte for ambígua.

Tudo bem, então vamos supor que a lebre e a tartaruga se encontrem em um ponto a k passos do início do ciclo, o número de passos antes do início do ciclo é mu e a duração do ciclo é L.

Então agora no ponto de encontro ->

Distância percorrida pela tartaruga = mu + a * L + k - Equação 1

(Etapas realizadas para alcançar o início do ciclo + etapas realizadas para cobrir as iterações 'a' do ciclo + k etapas desde o início do ciclo) (onde a é alguma constante positiva)

Distância percorrida pela lebre = mu + b * L + k - Equação 2

(Etapas realizadas para alcançar o início do ciclo + etapas realizadas para cobrir as iterações 'b' do ciclo + k etapas desde o início do ciclo) (onde b é uma constante positiva eb> = a)

Portanto, a distância extra percorrida pela lebre é = Equação 2 - Equação 1 = (ba) * L

Observe que essa distância também é igual à distância da tartaruga a partir do ponto de partida, pois a lebre se move 2 vezes mais rápido que a tartaruga. Isso pode ser equiparado a 'mu + k', que também é a distância do ponto de encontro desde o início, se não incluirmos várias travessias do ciclo.

Assim, mu + k = (ba) * L

Portanto, mu passos deste ponto levariam ao início do ciclo (já que k passos do início do ciclo já foram dados para chegar ao ponto de encontro). Isso pode acontecer no mesmo ciclo ou em qualquer um dos ciclos subsequentes. Portanto, agora, se movermos a tartaruga para o início da lista vinculada, serão necessárias muitas etapas para atingir o ponto inicial do ciclo e a lebre tomará várias etapas para também alcançar o início do ciclo e, portanto, ambos se encontrarão no local. ponto de partida do ciclo.

PS: Sinceramente, eu tinha a mesma pergunta que o pôster original e li a primeira resposta, eles esclareceram algumas coisas, mas eu não consegui chegar ao resultado final com clareza e tentei fazer do meu jeito e achou mais fácil de entender.

crédito de imagem

Distância da chamada: o número de links que um ponteiro segue e cronometra o número de iterações que o algoritmo leva para mover o link lento do ponteiro um e o link rápido do ponteiro dois. Existem N nós antes de um ciclo de comprimento C, rotulados com deslocamento de ciclo k = 0 a C-1.

Para chegar ao início do ciclo, lento leva N tempo e distância. Isso significa que a distância N é rápida no ciclo (N para chegar lá, N para girar). Portanto, no tempo N, lento está no deslocamento do ciclo k = 0 e rápido está no deslocamento do ciclo k = N mod C.

Se N mod C for zero, lento e rápido agora correspondem e o ciclo é encontrado no tempo N e na posição do ciclo k = 0.

Se N mod C não for zero, então rápido agora precisa acompanhar a velocidade lenta, que no momento N é a distância C- (N mod C) atrasada no ciclo.

Como o movimento rápido 2 para cada 1 de velocidade lenta, reduzindo a distância em 1 em cada iteração, leva tanto tempo adicional quanto a distância entre rápida e lenta no tempo N, que é C- (N mod C). Como o slow está se movendo do deslocamento 0, esse também é o deslocamento onde eles se encontram.

Portanto, se N mod C for zero, a fase 1 será interrompida após N iterações no início do ciclo. Caso contrário, a fase 1 para após as iterações N + C- (N mod C) no deslocamento C- (N mod C) no 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, então fase 2: lento toma N mais etapas para chegar ao ciclo, nesse ponto rápido (agora movendo-se 1 por etapa de tempo) está em (C- (N mod C) + N) mod C = 0. Então eles se encontram no início do ciclo após a fase 2.

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

Para completar, a fase 3 calcula a duração do ciclo, movendo-se mais uma vez pelo ciclo:

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

Reduza o problema para um problema de loop e volte ao problema inicial

Acho a explicação a seguir mais intuitiva.

1. Pegue dois ponteiros ( 1 = tartaruga e 2 = lebre) que começam na cabeça ( O ), 1 tem um comprimento de passo de 1 , 2 tem um comprimento de passo de 2 . Pense no momento em que 1 atinge o nó inicial desse ciclo ( A ).

   Queremos responder à seguinte pergunta "Onde está 2 quando 1 está em A?" .

   Então, OA = aé um número natural ( a >= 0). Mas pode ser escrito da seguinte maneira:, a = k*n + bonde a, k, n, b are natural numbers:

   • n = a duração do ciclo
   • k >= 0 = constante
   • 0 <= b <= n-1

   Isso significa isso b = a % n.

   Por exemplo: se a = 20e n = 8=> k = 2e b = 4porque 20 = 2*8 + 4.

   A distância percorrida por 1 é d = OA = a = k*n + b. Mas, ao mesmo tempo, 2 capas D = 2*d = d + d = OA + d = OA + k*n + b. Isso significa que quando 2 está em A, ele deve ser coberto k*n + b. Como você pode ver, ké o número de voltas, mas após essas voltas, 2 estará b longe de A. Então, descobrimos onde 2 é quando 1 está em A. Vamos chamar esse ponto B, onde AB = b.

   

2. Agora, reduzimos o problema para um círculo. A pergunta é "Onde está o ponto de encontro?" . Onde é esse C ?

   

   Em cada etapa, 2 reduz a distância de 1 com 1(digamos, medidor) porque 1 está se afastando de 2 com 1, mas ao mesmo tempo 2 se aproxima de 1 por 2.

   Portanto, a interseção será quando a distância entre 1 e 2 for zero. Isso significa que 2 reduz a n - bdistância. Para conseguir isso, 1 fará n - betapas, enquanto 2 fará 2*(n - b)etapas.

   Portanto, o ponto de interseção estará n - blonge de A (sentido horário), porque essa é a distância percorrida por 1 até encontrar 2 . => a distância entre C e A é CA = bporque AC = AB + BC = n - be CA = n - AC. Não pense que AC = CA, como a ACdistância não é uma distância matemática trivial, é o número de etapas entre A e C (onde A é o ponto inicial e C é o ponto final).

3. Agora, voltemos ao esquema inicial.

   Nós sabemos disso a = k*n + be CA = b.

   Podemos pegar 2 novos ponteiros 1 ' e 1' ' , onde 1' começa a partir da cabeça ( O ) e 1 '' começa a partir do ponto de interseção ( C ).

   Enquanto 1 ' passa de O para A , 1' ' passa de C para A e continua a terminar as kvoltas. Assim, o ponto de intersecção é Um .

   

   

Se os ponteiros se encontrarem no ponto P, como mostra a figura, a distância Z + Y é o ponto P e X + Y também é o ponto P, o que significa Z = X. É por isso que continuar movendo um ponteiro de P e outro do início (S) até que se encontrem, o que significa mover uma distância igual (Z ou X) para o mesmo ponto M (distância Z de P e X de S) será o início do loop. Simples!

Com toda a análise acima, se você é uma pessoa que aprende pelo exemplo, tentei escrever uma breve análise e exemplo que ajude a explicar a matemática que todos os outros tentaram explicar. Aqui vamos nós!

Análise:

Se tivermos dois ponteiros, um mais rápido que o outro, e movê-los juntos, eles se encontrarão novamente para indicar um ciclo ou nulo para indicar nenhum ciclo.

Para encontrar o ponto de partida do ciclo, deixe ...

1. m seja a distância da cabeça até o início do ciclo;

2. d ser o número de nós no ciclo;

3. p1 seja a velocidade do ponteiro mais lento;

4. p2seja a velocidade do ponteiro mais rápido, por exemplo. 2 significa etapas através de dois nós por vez.

   Observe as seguintes iterações:

 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 dos dados de amostra acima, podemos descobrir facilmente que sempre que os ponteiros mais rápidos e mais lentos se encontram, eles estão a alguns mpassos do início do ciclo. Para resolver isso, coloque o ponteiro mais rápido de volta na cabeça e defina sua velocidade para a velocidade do ponteiro mais lento. Quando eles se reencontram, o nó é o início do ciclo.

Digamos,

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

temos 2 ponteiros A e B, A roda a uma velocidade 1x, B a uma velocidade 2x, ambos começam no início.

quando A atingir N [0], B já deve estar em N [m]. (Nota: A usa m etapas para alcançar N [0] e B deve ser m etapas adicionais)

Então, A executa k mais etapas para colidir com B, ou seja, A está em N [k], B está em N [m + 2k] (Nota: B deve executar duas etapas a partir de N [m])

Uma colisão B em N [k] e N [m + 2k], respectivamente, significa k = m + 2k, portanto, k = -m

Assim, para voltar ao N [0] de N [k], precisamos de mais m passos.

Simplesmente dizendo, precisamos executar m mais etapas depois de encontrarmos o nó de colisão. Podemos ter um ponteiro para executar desde o início e um ponteiro para executar no nó de colisão, eles se encontrarão em N [0] após m etapas.

Portanto, o pseudo-código é o seguinte:

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

Não acho que seja verdade que, quando eles se encontrem, esse seja o ponto de partida. Mas sim, se o outro ponteiro (F) estava no ponto de encontro anterior, esse ponteiro estará no final do loop, em vez do início do loop, e o ponteiro (S), que começou no início da lista, será acabam no início do loop. por exemplo:

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;
}

Uma explicação simples usando a idéia de velocidade relativa ensinada no ensino médio - aulas de Física 101 / Cinemática.

1. Vamos assumir que a distância entre o início da lista vinculada e o início do círculo é de xsaltos. Vamos chamar o início do círculo como ponto X(em maiúsculas - veja a figura acima). Suponhamos também que o tamanho total do círculo seja N saltos.

2. Velocidade da lebre = 2 * Velocidade da tartaruga. Então isso é 1 hops/sece 2 hops/secrespectivamente

3. Quando a tartaruga atinge o início do círculo X, a lebre deve ainda mais xsaltar no ponto Yda figura. (Porque a lebre percorreu o dobro da distância que a tartaruga).

4. Assim, o comprimento do arco restante no sentido horário de X a Y seria N-x. Essa também é a distância relativa a ser percorrida entre a lebre e a tartaruga para que eles possam se encontrar . Digamos que essa distância relativa será coberta em tempo, t_mou seja, na hora de encontrar. A velocidade relativa é (2 hops/sec - 1 hops/sec)ie 1 hops/sec. Assim, usando distância relativa = velocidade relativa X tempo, obtemos t= N-xseg. Por isso, é preciso N-xchegar ao ponto de encontro da tartaruga e da lebre.

5. Agora em N-xsegundos e em 1 hops/secalta velocidade, a tartaruga que estava no ponto anterior Xcobrirá os saltos de Nx para chegar ao ponto de encontro M. Portanto, isso significa que o ponto de encontro Mestá no N-xlúpulo no sentido anti-horário de X= (o que implica ainda mais) => que existe uma xdistância restante do ponto Mao Xsentido horário.

6. Mas xtambém é a distância para chegar ao ponto Xdesde o início da lista vinculada.

7. Agora, não nos importamos com o número de saltos x. Se colocarmos uma tartaruga no início do LinkedList e uma tartaruga no ponto de encontro Me deixá-los pular / andar, eles se encontrarão no ponto X, que é o ponto (ou nó) que precisamos.

Trabalhar isso com um diagrama ajudaria. Estou tentando explicar o problema sem equações.

1. Se deixarmos a lebre e a tartaruga correrem em círculo e a lebre correr duas vezes, então, no final de uma volta, a tartaruga-lebre estará na metade. No final de duas voltas, a tartaruga-lebre teria feito 1 volta e os dois se encontraram. Isso se aplica a todas as velocidades, como se a lebre corre três vezes, a lebre 1 volta é igual a 1/3 da tartaruga; portanto, no final de 3 voltas, a tartaruga lebre teria coberto 1 volta e elas se encontram.
2. Agora, se os iniciarmos m passos antes do loop, significa que a lebre mais rápida está começando no loop. Portanto, se a tartaruga atingir o início do loop, a lebre estará m passos à frente do loop e, quando eles se encontrarem, haverá m passos antes do início do loop.

-Existem k etapas antes do loop. Não sabemos o que é k e não precisamos descobrir. Podemos trabalhar abstratamente com apenas k.

- Após as etapas k

----- T está no início do ciclo

----- H é k entra em ciclo (ele subiu 2k no total e, portanto, k entrou em loop)

** eles agora estão em tamanho loops - separados por k

(observe que k == K == mod (tamanho do loop, k) - ou seja, se um nó está 2 etapas em um ciclo de 5 nós, também são 7, 12 ou 392 etapas; portanto, qual o tamanho do ciclo? fator em.

Como eles se alcançam na velocidade de 1 passo por unidade de tempo, porque um está se movendo duas vezes mais rápido que o outro, eles se encontrarão no tamanho loops - k.

Isso significa que serão necessários k nós para alcançar o início do ciclo e, portanto, a distância da cabeça ao início do ciclo e da colisão ao início do ciclo é a mesma.

Então agora, após a primeira colisão, mova T de volta à cabeça. T e H se encontrarão no início do ciclo, se você se mover na taxa de 1 cada. (em k etapas para ambos)

Isso significa que o algoritmo é:

• da cabeça mova T = t.next e H.next.next até que colidam (T == H) (existe um ciclo)

// cuide do caso em que k = 0 ou T e H se encontrem na cabeça do loop, calculando o comprimento do loop

- conte a duração do ciclo movendo T ou H ao redor dele com um contador

- mover um ponteiro T2 para o cabeçalho da lista

--move o comprimento do ponteiro das etapas do ciclo

- mova outro ponteiro H2 para a cabeça

- mova T2 e H2 em conjunto até que se encontrem no início do ciclo

é isso aí!

Já existem muitas respostas para isso, mas uma vez criei um diagrama mais intuitivo visualmente para mim. Talvez possa ajudar outras pessoas.

Os principais momentos aha para mim foram:

• Divida T (tartaruga) em T1 (pré-loop) e T2 (in-loop).

• Subtraia T de H , onde eles se sobrepõem visualmente. O que resta ( H - T = H ' ) é igual a T .

• A matemática restante é bastante simples.

Sei que já existe uma resposta aceita para esse problema, mas ainda tentarei responder de maneira fluida. Presumir :

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.

Agora, deixe a lebre e a tartaruga se encontrarem depois do tempo 't' desde o início.

Observações:

Se, Distância percorrida pela tartaruga = v * t = x + (bk) (digamos)

Então, a distância percorrida pela lebre = 2 * v * t = x + (b - k) + b (uma vez que a lebre já atravessou a parte em loop uma vez)

Agora, os horários das reuniões são os mesmos.

Qual é o valor de x?

=> x = k

Naturalmente, isso significa que o comprimento do caminho que não está em loop é o mesmo que a distância do ponto inicial do loop a partir do ponto em que ambos se encontram.

Na verdade, é fácil provar que os dois se encontrarão no ponto de partida, se você considerar a matemática por trás do ponto de encontro.
Em primeiro lugar, deixe m denotar o ponto de ciclo na lista ligada de partida, e N denota o comprimento do ciclo. Então, para a lebre e a tartaruga se encontrarem, temos:

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

Afirmando isso mais matematicamente:

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

para que se encontrem no momento t, que deve ser múltiplo da duração do ciclo. Isso significa que eles se reúnem em um local que é (t-m) modulo n = (0-m) modulo n = (-m) modulo n .

Então agora voltando à pergunta, se você mover um ponteiro do início da lista vinculada e outro do ponto de interseção, após m etapas, teremos a lebre (que está se movendo dentro do ciclo) chegar a um ponto que é ((-m) + m) modulo n = 0 modulo nque nada mais é do que o ponto de partida do ciclo. Então, podemos ver que, após m etapas, chega ao início do ciclo e a tartaruga o encontra lá, pois irá atravessar m etapas desde o início da lista vinculada.

Como observação lateral, também podemos calcular o tempo de sua interseção da seguinte maneira: A condição t = 0 modulo nnos diz que eles se encontrarão em um momento múltiplo da duração do ciclo, e também t deve ser maior que m, como se reuniriam em o ciclo . Portanto, o tempo gasto será igual ao primeiro múltiplo de n, que é maior que m .

Suponha que seus ponteiros se encontrem na interseção dos pontos ye z.

n e m são o número de loops mais rápido e mais lento que o ponteiro leva, respectivamente, antes da reunião.

Consulte a imagem para o restante da prova. Encontre o ponto inicial do loop na lista vinculada