Prova de detecção do início do ciclo na lista vinculada [duplicado]
Esta pergunta já tem uma resposta aqui:
Explicar como encontrar o nó de início do ciclo na lista vinculada ao cicl 20 respostasDe várias postagens dentro e fora do stackover, aprendi a detectar ciclos em uma lista vinculada, a duração de um ciclo. Eu também encontrei o método de como detectar o início do loo
qui estão os passos novamente para referênci
Detecting Loop:
Tem duas dicas, classicamente chamadas de lebre e tartaruga. Mova a lebre em duas etapas e a tartaruga em 1. Se elas se encontrarem em algum momento, certamente haverá um ciclo e o ponto de encontro estará obviamente dentro do cicl
Comprimento do laço:
Mantenha um ponteiro fixo no ponto de encontro enquanto incrementa o outro até que eles sejam iguais novamente. Incremente um contador à medida que avança e o valor do contador em meet será a duração do cicl
Encontre o início do ciclo
Pegue um ponteiro para iniciar a lista e mantenha o outro no ponto de encontro. Agora, incremente ambos em um e o ponto de encontro é o início do loop. Verifiquei o método usando alguns casos no papel, mas não entendo por que ele deve funciona
lguém pode fornecer uma prova matemática de por que esse método funcion