Expliquez comment la recherche du nœud de début de cycle dans la liste chaînée de cycle fonctionne?

Je comprends que la réunion de Tortoise et Hare conclut l'existence de la boucle, mais comment le déplacement de la tortue au début de la liste chaînée tout en gardant le lièvre au lieu de rencontre, suivi du déplacement des deux pas à pas les fait se rencontrer au point de départ du cycle?

Il s'agit de l'algorithme de Floyd pour la détection de cycle . Vous vous interrogez sur la deuxième phase de l'algorithme - une fois que vous avez trouvé un nœud faisant partie d'un cycle, comment trouver le début du cycle?

Dans la première partie de l'algorithme de Floyd, le lièvre se déplace de deux pas pour chaque pas de la tortue. Si jamais la tortue et le lièvre se rencontrent, il y a un cycle et le point de rencontre fait partie du cycle, mais pas nécessairement le premier nœud du cycle.

Lorsque la tortue et le lièvre se rencontrent, nous avons trouvé le plus petit i (le nombre de pas effectués par la tortue) tel que X _i = X _2i . Soit mu le nombre d'étapes pour aller de X ₀ au début du cycle, et soit lambda représente la longueur du cycle. Alors i = mu + a lambda, et 2i = mu + b lambda, où a et b sont des nombres entiers indiquant combien de fois la tortue et le lièvre ont fait le tour du cycle. La soustraction de la première équation de la seconde donne i = (ba) * lambda, donc i est un multiple entier de lambda. Par conséquent, X _{i + mu} = X _mu . X _i représente le point de rencontre de la tortue et du lièvre. Si vous ramenez la tortue au nœud de départ X₀ , et que la tortue et le lièvre continuent à la même vitesse, après mu étapes supplémentaires, la tortue aura atteint X _mu , et le lièvre aura atteint X _{i + mu} = X _mu , donc le deuxième point de rencontre indique le début de la cycle.

Laissez-moi essayer de clarifier l'algorithme de détection de cycle qui est fourni à http://en.wikipedia.org/wiki/Cycle_detection#Tortoise_and_hare dans mes propres mots.

Comment ça fonctionne

Prenons une tortue et un lièvre (nom des pointeurs) pointant vers le début de la liste avec un cycle, comme dans le diagramme ci-dessus.

Supposons que si nous déplaçons la tortue d'un pas à la fois, et le lièvre de 2 pas à la fois, ils finiront par se rencontrer à un moment donné. Montrons que tout d'abord cette hypothèse est vraie.

La figure illustre une liste avec un cycle. Le cycle a une longueur de net nous sommes initialement à mquelques pas du cycle. Disons également que le point de rencontre est à kquelques pas du début du cycle et que la tortue et le lièvre se rencontrent lorsque la tortue a franchi ile pas. (Hare aurait alors franchi 2ile pas.)

Les 2 conditions suivantes doivent être remplies:

1) i = m + p * n + k

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

Le premier dit que la tortue bouge i pas et dans ces iétapes, elle arrive d'abord au cycle. Ensuite, il passe par les ptemps de cycle pour un nombre positif p. Enfin, il passe sur kplus de nœuds jusqu'à ce qu'il rencontre le lièvre.

Un semblable est vrai pour le lièvre. Il déplace des 2iétapes et dans ces2i étapes, il arrive d'abord au cycle. Ensuite, il passe par les qtemps de cycle pour un nombre positif q. Enfin, il passe sur kplus de nœuds jusqu'à ce qu'il rencontre la tortue.

Comme le lièvre voyage avec le double de la vitesse de la tortue, le temps est constant pour les deux lorsqu'ils atteignent le point de rencontre.

Donc, en utilisant une simple relation vitesse, temps et distance,

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

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

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

Parmi m, n, k, p, q, les deux premiers sont des propriétés de la liste donnée. Si nous pouvons montrer qu'il existe au moins un ensemble de valeurs pour k, q, p qui rend cette équation vraie, nous montrons que l'hypothèse est correcte.

Un tel ensemble de solutions est le suivant:

p = 0

q = m

k = m n - m

Nous pouvons vérifier que ces valeurs fonctionnent comme suit:

m + k = ( q - 2p ) n  

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

=> mn = mn.

Pour cet ensemble, iest

i = m + p n + k

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

Bien sûr, vous devriez voir que ce n'est pas forcément le plus petit possible. En d'autres termes, la tortue et le lièvre se sont peut-être déjà rencontrés plusieurs fois. Cependant, comme nous montrons qu'ils se rencontrent à un moment donné au moins une fois, nous pouvons dire que l'hypothèse est correcte. Donc, ils devraient se rencontrer si nous déplaçons l'un d'eux d'un pas, et l'autre de deux pas à la fois.

Nous pouvons maintenant passer à la deuxième partie de l'algorithme qui est de savoir comment trouver le début du cycle.

Début du cycle

Une fois que la tortue et le lièvre se rencontrent, remettons la tortue au début de la liste et gardons le lièvre là où ils se sont rencontrés (ce qui est à k pas du début du cycle).

L'hypothèse est que si nous les laissons se déplacer à la même vitesse (1 pas pour les deux), la première fois qu'ils se reverront sera le début du cycle.

Prouvons cette hypothèse.

Supposons d'abord qu'un oracle nous dise ce qu'est m.

Ensuite, si nous les laissons se déplacer de m + k pas, la tortue devra arriver au point où elle s'est rencontrée à l'origine (à k pas du début du cycle - voir sur la figure).

Auparavant, nous l'avons montré m + k = (q - 2p) n.

Puisque m + k pas est un multiple de la longueur du cycle n, le lièvre, dans le même temps, passerait par les temps du cycle (q-2p) et reviendrait au même point (à k pas du début du cycle).

Maintenant, au lieu de les laisser bouger de m + k pas, si on les laisse se déplacer seulement de m pas, la tortue arriverait au début du cycle. Hare serait à k étapes avant d'effectuer des rotations (q-2p). Puisqu'il a commencé k étapes avant le début du cycle, le lièvre devrait arriver au début du cycle.

En conséquence, cela explique qu'ils devraient se rencontrer au début du cycle après un certain nombre d'étapes pour la toute première fois (la toute première fois car la tortue vient d'arriver au cycle après m étapes et elle ne pourrait jamais voir le lièvre qui était déjà en le cycle).

Nous savons maintenant que le nombre de pas dont nous avons besoin pour les déplacer jusqu'à ce qu'ils se rencontrent s'avère être la distance entre le début de la liste et le début du cycle, m. Bien entendu, l'algorithme n'a pas besoin de savoir ce qu'est m. Il ne fera que déplacer la tortue et le lièvre un pas à la fois jusqu'à ce qu'ils se rencontrent. Le point de rencontre doit être le début du cycle et le nombre de pas doit être la distance (m) du début du cycle. En supposant que nous connaissons la longueur de la liste, nous pouvons également calculer la longueur du cycle de soustraction de m de la longueur de la liste.

Référez cette image:

Distance parcourue par slowPointer avant la rencontre = x + y

Distance parcourue par fastPointer avant la réunion = (x + y + z) + y = x + 2y + z

Puisque fastPointer se déplace avec le double de la vitesse de slowPointer, et le temps est constant pour les deux quand ils atteignent le point de rencontre.

Donc en utilisant une relation simple vitesse, temps et distance 2 (x + y) = x + 2y + z => x + 2y + z = 2x + 2y => x = z

Par conséquent, en déplaçant slowPointer au début de la liste liée, et en faisant à la fois slowPointer et fastPointer pour déplacer un nœud à la fois, ils ont tous deux la même distance à parcourir .

Ils atteindront le point où la boucle commence dans la liste chaînée.

_{La réponse simple et sous-votée d'Old Monk explique comment trouver le cycle lorsque le coureur rapide ne termine qu'un seul cycle complet. Dans cette réponse, j'explique le cas où le coureur rapide a exécuté la boucle plusieurs fois avant que le coureur lent entre dans la boucle.}

En utilisant la même image:

Disons que le coureur rapide a exécuté la boucle m fois avant une rencontre lente et rapide. Cela signifie que:

• Distance parcourue lentement: x + y
• Distance parcourue par rapide: x + m (y + z) + y soit extra y là où ils se rencontrent

Étant donné que les courses rapides avec deux fois la vitesse de la lenteur et qu'elles courent depuis le même temps, cela implique que si nous doublons la distance parcourue par la lenteur, nous obtenons la distance parcourue rapidement. Donc,

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

La résolution de x donne,

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

Dans un scénario réel, cela signifierait, x = (m - 1) boucle complète + une distance supplémentaire z .

Par conséquent, si nous mettons un pointeur au début de la liste et laissons l'autre au point de rendez-vous, alors les déplacer à la même vitesse entraînera le pointeur en boucle complétant m - 1 exécutions de la boucle, puis rencontrant l'autre. pointeur juste au début de la boucle.

C'est très très simple. Vous pouvez penser en termes de vitesse relative. Si le lapin bouge de deux nœuds et que la tortue déplace un nœud, par rapport à la tortue, le lapin déplace un nœud (supposons que la tortue est au repos). Donc, si nous déplaçons un nœud dans la liste chaînée circulaire, nous allons certainement nous revoir à ce stade.

Après avoir trouvé le point connecté à l'intérieur de la liste liée circulaire, le problème est maintenant réduit à la recherche du point d'intersection de deux problèmes de liste liée.

Au moment de la première collision, la tortue a fait m + k pas comme indiqué ci-dessus. Le lièvre se déplace deux fois plus vite que la tortue, ce qui signifie que le lièvre a fait 2 (m + k) pas. De ces simples faits, nous pouvons déduire le graphique suivant.

À ce stade, nous remettons la tortue au point de départ et déclarons que le lièvre et la tortue doivent bouger un pas à la fois. Par définition, après m étapes, la tortue sera au début du cycle. Où sera le lièvre?

Hare sera également au début du cycle. Ceci est clair à partir du deuxième graphique: lorsque la tortue a été ramenée au début, le lièvre était à k étapes dans son dernier cycle. Après m étapes, le lièvre aura terminé un autre cycle et est entré en collision avec la tortue.

Approche:

Il y a deux pointeurs:

• Un pointeur lent qui déplace un nœud à la fois.
• Un pointeur rapide qui déplace deux nœuds à la fois.

Si les deux pointeurs se rencontrent, cela prouve qu'il y a une boucle. Une fois qu'ils se sont rencontrés, l'un des nœuds pointera vers la tête, puis les deux passeront un nœud à la fois. Ils se retrouveront au début de la boucle.

Justification: Lorsque deux personnes marchent sur une piste circulaire, l'une d'elles à deux fois la vitesse de l'autre, où se rencontrent-elles? Exactement là où ils ont commencé.

Maintenant, supposons que le coureur rapide ait une longueur d'avance sur les kpas dans un ntour de pas. où vont-ils se rencontrer? Exactement par n-kétapes. Lorsque le coureur lent a parcouru les (n-k)étapes, le coureur rapide aurait couvert les k+2(n-k)étapes. ( c.-à-d. k+2n-2kétapes c. 2n-k-à -d. c'est à dire(n-k) étapes (le chemin est circulaire et nous ne sommes pas préoccupés par le nombre de tours après lesquels ils se rencontrent; nous nous intéressons simplement à la position où ils se rencontrent).

Maintenant, comment le coureur rapide a-t-il pris une longueur d'avance sur les kétapes en premier lieu? Parce qu'il a fallu au coureur lent autant de pas pour atteindre le début de la boucle. Ainsi, le début de la boucle est à k pas du nœud principal.

Remarque: Le nœud où les deux pointeurs se rencontrent est à kquelques pas du début de la boucle (à l'intérieur de la boucle) et le nœud principal est également à kquelques pas du début de la boucle. Ainsi, lorsque le pointeur avance à un rythme égal de 1 pas à partir de ces nœuds, ils se rencontrent au début de la boucle.

Je pense que c'est simple. S'il vous plaît laissez-moi savoir si une partie est ambiguë.

Bon, supposons que le lièvre et la tortue se rencontrent à un point situé à k pas du début du cycle, le nombre d'étapes avant le début du cycle est mu et la durée du cycle est L.

Alors maintenant au point de rencontre ->

Distance parcourue par la tortue = mu + a * L + k - Équation 1

(Étapes prises pour atteindre le début du cycle + étapes prises pour couvrir les itérations 'a' du cycle + k étapes à partir du début du cycle) (où a est une constante positive)

Distance parcourue par le lièvre = mu + b * L + k - Équation 2

(Étapes prises pour atteindre le début du cycle + étapes prises pour couvrir les itérations 'b' du cycle + k étapes à partir du début du cycle) (où b est une constante positive et b> = a)

Donc la distance supplémentaire parcourue par le lièvre est = Equation 2 - Equation 1 = (ba) * L

Veuillez noter que cette distance est également égale à la distance entre la tortue et le point de départ puisque le lièvre se déplace 2 fois plus vite que la tortue. Cela peut être assimilé à «mu + k» qui est également la distance du point de rencontre depuis le début si nous n'incluons pas plusieurs traversées du cycle.

Ainsi, mu + k = (ba) * L

Ainsi, mu pas à partir de ce point ramèneraient au début du cycle (puisque k étapes depuis le début du cycle ont déjà été franchies pour atteindre le point de rencontre). Cela peut se produire dans le même cycle ou dans l'un des cycles suivants. Ainsi maintenant, si nous déplaçons la tortue au début de la liste chaînée, il faudra mu étapes pour atteindre le point de départ du cycle et le lièvre prendrait mu étapes pour atteindre également le début du cycle et ainsi ils se rencontreraient tous les deux au point de départ du cycle.

PS Honnêtement, j'avais la même question que l'affiche originale dans mon esprit et j'ai lu la première réponse, ils ont clarifié certaines choses mais je ne pouvais pas arriver au résultat final clairement et j'ai donc essayé de le faire à ma manière et trouvé plus facile à comprendre.

crédit d'image

Distance d'appel: le nombre de liens suivis par un pointeur et le nombre d'itérations que l'algorithme prend pour déplacer le pointeur lent d'un lien et le pointeur rapide de deux liens. Il y a N nœuds avant un cycle de longueur C, étiquetés avec le décalage de cycle k = 0 à C-1.

Pour atteindre le début du cycle, lent prend N temps et distance. Cela signifie que rapide prend N distance dans le cycle (N pour y arriver, N pour tourner). Ainsi, au temps N, lent est au décalage de cycle k = 0, et rapide est au décalage de cycle k = N mod C.

Si N mod C est nul, lent et rapide correspondent maintenant et le cycle est trouvé au temps N et la position de cycle k = 0.

Si N mod C n'est pas nul, alors rapide doit maintenant rattraper le lent, qui au temps N est la distance C- (N mod C) en arrière dans le cycle.

Puisque rapide se déplace de 2 pour chaque 1 de lent, réduisant la distance de 1 à chaque itération, cela prend autant de temps supplémentaire que la distance entre rapide et lent au temps N, qui est C- (N mod C). Puisque lent se déplace à partir du décalage 0, c'est également le décalage où ils se rencontrent.

Ainsi, si N mod C est nul, la phase 1 s'arrête après N itérations au début du cycle. Sinon, la phase 1 s'arrête après N + C- (N mod C) itérations au décalage C- (N mod C) dans le cycle.

// 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, donc la phase 2: slow prend N pas de plus pour arriver au cycle, à quel point rapide (se déplaçant maintenant de 1 par pas de temps) est à (C- (N mod C) + N) mod C = 0. Donc ils se rencontrent au début du cycle après la phase 2.

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

Par souci d'exhaustivité, la phase 3 calcule la longueur du cycle en se déplaçant à nouveau dans le cycle:

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

Réduisez le problème à un problème de boucle, puis revenez au problème initial

Je trouve l'explication suivante plus intuitive.

1. Prenez deux pointeurs ( 1 = tortue et 2 = lièvre) qui partent de la tête ( O ), 1 a une longueur de pas de 1 , 2 a une longueur de pas de 2 . Pensez au moment où 1 atteint le nœud de début de ce cycle ( A ).

   Nous voulons répondre à la question suivante "Où est 2 quand 1 est dans A?" .

   Donc, OA = aest un nombre naturel ( a >= 0). Mais il peut s'écrire de la manière suivante:, a = k*n + boù a, k, n, b are natural numbers:

   • n = la durée du cycle
   • k >= 0 = constante
   • 0 <= b <= n-1

   Cela signifie que b = a % n.

   Par exemple: si a = 20et n = 8=> k = 2et b = 4parce que 20 = 2*8 + 4.

   La distance couverte par 1 est d = OA = a = k*n + b. Mais dans le même temps, 2 couvertures D = 2*d = d + d = OA + d = OA + k*n + b. Cela signifie que lorsque 2 est dans A, il doit couvrir k*n + b. Comme vous pouvez le voir, kc'est le nombre de tours, mais après ces tours, 2 sera b loin de A. Donc, nous avons trouvé où 2 est quand 1 est dans A. Appelons ce point B, où AB = b.

   

2. Maintenant, nous réduisons le problème à un cercle. La question est "Où est le point de rencontre?" . Où est ce C ?

   

   Dans chaque étape, 2 réduit la distance de 1 avec 1(LET mètres de la parole) , car 1 devient de plus de 2 avec 1, mais en même temps 2 va plus proche de 1 par 2.

   Ainsi, l'intersection sera lorsque la distance entre 1 et 2 sera nulle. Cela signifie que 2 réduit la n - bdistance. Pour y parvenir, 1 fera des n - bétapes, tandis que 2 fera des 2*(n - b)étapes.

   Ainsi, le point d'intersection sera n - béloigné de A (sens horaire), car c'est la distance parcourue par 1 jusqu'à ce qu'il rencontre 2 . => la distance entre C et A est CA = b, parce que AC = AB + BC = n - bet CA = n - AC. Ne pensez pas que AC = CA, parce que la ACdistance n'est pas une distance mathématique triviale, c'est le nombre de pas entre A et C (où A est le point de départ et C est le point final).

3. Maintenant, revenons au schéma initial.

   Nous savons que a = k*n + betCA = b .

   Nous pouvons prendre 2 nouveaux pointeurs 1 ' et 1' ' , où 1' part de la tête ( O ) et 1 '' part du point d'intersection ( C ).

   Alors que 1 ' va de O à A , 1' ' va de C à A et continue de terminer des ktours. Ainsi, le point d'intersection est un .

   

   

Si les pointeurs se rencontrent en un point P comme indiqué sur la figure, la distance Z + Y est le point P et X + Y est également le point P ce qui signifie Z = X. C'est pourquoi continuer à déplacer un pointeur de P et en déplacer un autre du début (S) jusqu'à ce qu'ils se rencontrent, ce qui signifie déplacer une distance égale (Z ou X) vers le même point M (distance Z de P et X de S) sera le démarrage de la boucle. Facile!

Avec toute l'analyse ci-dessus, si vous êtes une personne qui apprend par l'exemple, j'ai essayé de rédiger une brève analyse et un exemple qui aident à expliquer les mathématiques que tout le monde a tenté d'expliquer. Et c'est parti!

Une analyse:

Si nous avons deux pointeurs, l'un plus rapide que l'autre, et que nous les déplaçons ensemble, ils finiront par se retrouver pour indiquer un cycle ou nul pour indiquer l'absence de cycle.

Pour trouver le point de départ du cycle, laissez ...

1. m être la distance entre la tête et le début du cycle;

2. d être le nombre de nœuds dans le cycle;

3. p1 être la vitesse du pointeur le plus lent;

4. p2être la vitesse du pointeur le plus rapide, par exemple. 2 signifie passer par deux nœuds à la fois.

   Observez les itérations suivantes:

 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

À partir des exemples de données ci-dessus, nous pouvons facilement découvrir que chaque fois que les pointeurs les plus rapides et les plus lents se rencontrent, ils sont à mquelques pas du début du cycle. Pour résoudre ce problème, replacez le pointeur le plus rapide sur la tête et réglez sa vitesse sur la vitesse du pointeur le plus lent. Lorsqu'ils se rencontrent à nouveau, le nœud est le début du cycle.

Disons,

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

nous avons 2 pointeurs A et B, A tourne à 1x vitesse, B à 2x vitesse, les deux commencent au début.

quand A atteint N [0], B devrait déjà être dans N [m]. (Remarque: A utilise m étapes pour atteindre N [0], et B devrait être m étapes supplémentaires)

Ensuite, A exécute k étapes supplémentaires pour entrer en collision avec B, c'est-à-dire que A est à N [k], B est à N [m + 2k] (Remarque: B devrait courir pendant 2k étapes à partir de N [m])

Une collision B à N [k] et N [m + 2k] respectivement, cela signifie k = m + 2k, donc k = -m

Ainsi, pour revenir au N [0] à partir de N [k], nous avons besoin de m étapes supplémentaires.

En termes simples, nous avons juste besoin d'exécuter m étapes supplémentaires après avoir trouvé le nœud de collision. Nous pouvons avoir un pointeur à exécuter depuis le début et un pointeur à partir du nœud de collision, ils se rencontreront à N [0] après m étapes.

Par conséquent, le pseudo code est le suivant:

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

Je ne pense pas que ce soit vrai que quand ils se rencontrent, c'est le point de départ. Mais oui si l'autre pointeur (F) était au point de rencontre avant, alors ce pointeur sera à la fin de la boucle au lieu du début de la boucle et le pointeur (S) qui a commencé au début de la liste il sera finissent au début de la boucle. par exemple:

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

Une explication simple utilisant l'idée de vitesse relative enseignée au lycée - Cours de physique 101 / cinématique.

1. Supposons que la distance entre le début de la liste liée et le début du cercle est un xsaut. Appelons le début du cercle comme point X(en majuscules - voir la figure ci-dessus). Supposons également que la taille totale du cercle soit de N sauts.

2. Vitesse du lièvre = 2 * Vitesse de la tortue. Donc c'est 1 hops/secet 2 hops/secrespectivement

3. Lorsque la tortue atteint le début du cercle X, le lièvre doit en outre être xhoublonné au point Yde la figure. (Parce que le lièvre a parcouru deux fois la distance que la tortue).

4. Ainsi, la longueur de l'arc restant dans le sens horaire de X à Y serait N-x. Il se trouve que c'est également la distance relative à parcourir entre le lièvre et la tortue pour qu'ils puissent se rencontrer . Disons que cette distance relative sera parcourue dans le temps, t_mc'est-à - dire le temps de se rencontrer. La vitesse relative est (2 hops/sec - 1 hops/sec)ie 1 hops/sec. Ainsi, en utilisant, distance relative = vitesse relative X temps, nous obtenons t= N-xsec. Il faudra donc N-xpour atteindre le point de rencontre pour la tortue et le lièvre.

5. Maintenant, en une N-xseconde et en 1 hops/secvitesse, la tortue qui était plus tôt au point Xcouvrira Nx sauts pour atteindre le point de rencontre M. Donc, cela signifie que le point de rencontre Mest à N-xsauts dans le sens antihoraire à partir de X= (ce qui implique en outre) => qu'il reste une xdistance entre le point Met le Xsens horaire.

6. Mais xc'est aussi la distance pour atteindre le point Xdepuis le début de la liste chaînée.

7. Maintenant, nous ne nous soucions pas du nombre de sauts xcorrespondant. Si nous mettons une tortue au début de la LinkedList et une tortue au point de rencontre Met les laissons sauter / marcher, alors elles se rencontreront au point X, qui est le point (ou nœud) dont nous avons besoin.

Travailler cela avec un diagramme aiderait. J'essaye d'expliquer le problème sans équations.

1. Si nous laissons le lièvre et la tortue courir en cercle et que le lièvre court deux fois la tortue, alors, à la fin d'un tour pour le lièvre, la tortue serait à moitié. Au bout de deux tours de lièvre, la tortue aurait fait 1 tour et ils se rencontrent tous les deux. Cela s'applique à toutes les vitesses comme si le lièvre court trois fois, le lièvre 1 tour est égal à 1/3 de la tortue donc à la fin de 3 tours pour le lièvre, la tortue aurait couvert 1 tour et ils se rencontrent.
2. Maintenant, si nous les démarrons m étapes avant la boucle, cela signifie que le lièvre le plus rapide commence en boucle. Donc, si la tortue atteint le début de la boucle, le lièvre est à m pas en avant de la boucle et quand ils se rencontrent, ce sera m pas avant le début de la boucle.

-il y a k étapes avant la boucle. Nous ne savons pas ce qu'est k et n'avons pas besoin de le découvrir. Nous pouvons travailler abstraitement avec seulement k.

--Après k étapes

----- T est au début du cycle

----- H est k étapes dans le cycle (il est passé 2k au total et donc k en boucle)

** ils sont maintenant en boucle - k séparés

(notez que k == K == mod (loopsize, k) --eg si un nœud est à 2 pas dans un cycle à 5 nœuds, il est également 7, 12 ou 392 pas, donc la taille du cycle par rapport à k n'est pas facteur de.

Puisqu'ils se rattrapent au rythme de 1 pas par unité de temps parce que l'un se déplace deux fois plus vite que l'autre, ils se rencontreront à la taille de la boucle - k.

Cela signifie qu'il faudra k nœuds pour atteindre le début du cycle et donc la distance de la tête au démarrage cyclique et la collision au démarrage cyclique sont les mêmes.

Alors maintenant, après la première collision, retournez T à la tête. T et H se rencontreront au démarrage cyclique si vous vous déplacez à une vitesse de 1 chacun. (en k pas pour les deux)

Cela signifie que l'algorithme est:

• de la tête déplace T = t.next et H.next.next jusqu'à ce qu'ils entrent en collision (T == H) (il y a un cycle)

// s'occupe du cas où k = 0 ou T et H se rencontrent en tête de boucle en calculant la longueur de la boucle

- compter la longueur du cycle en déplaçant T ou H autour de lui avec un compteur

- déplacer un pointeur T2 en tête de liste

- déplacer la longueur du pointeur des étapes du cycle

- déplacer un autre pointeur H2 vers la tête

- déplacer T2 et H2 en tandem jusqu'à ce qu'ils se rencontrent au début du cycle

c'est tout!

Il y a déjà beaucoup de réponses à cela, mais j'ai une fois proposé un diagramme pour cela qui est plus intuitif visuellement pour moi. Peut-être que cela peut aider d'autres personnes.

Les principaux moments aha pour moi ont été:

• Divisez T (tortue) en T1 (pré-boucle) et T2 (en boucle).

• Soustrayez T de H , où ils se chevauchent visuellement. Ce qui reste ( H - T = H ' ) est égal à T .

• Le calcul restant est assez simple.

Je sais qu'il existe déjà une réponse acceptée pour ce problème, mais je vais toujours essayer de répondre de manière fluide. Présumer :

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.

Maintenant, laissez le lièvre et la tortue se rencontrer après le temps 't' du début.

Observations:

Si, Distance parcourue par la tortue = v * t = x + (bk) (disons)

Ensuite, Distance parcourue par le lièvre = 2 * v * t = x + (b - k) + b (puisque le lièvre a déjà traversé la partie bouclée une fois)

Maintenant, les heures de réunion sont les mêmes.

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

=> x = k

Cela signifie bien sûr que la longueur du chemin qui n'est pas bouclé est la même que la distance entre le point de départ de la boucle et le point de rencontre des deux.

Il est en fait facile de prouver qu'ils se rencontreront tous les deux au point de départ, si l'on considère les calculs derrière le point de rencontre.
Soit d'abord m le point de départ du cycle dans la liste chaînée, et n la longueur du cycle. Ensuite, pour que le lièvre et la tortue se rencontrent, nous avons:

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

En disant cela de manière plus mathématique:

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

ils se rencontreront donc au temps t qui devrait être un multiple de la durée du cycle. Cela signifie qu'ils se rencontrent à un endroit, qui est (t-m) modulo n = (0-m) modulo n = (-m) modulo n.

Revenons maintenant à la question, si vous déplacez un pointeur du début de la liste chaînée et un autre du point d'intersection, après m étapes, nous aurons le lièvre (qui se déplace à l'intérieur du cycle) en un point qui est ((-m) + m) modulo n = 0 modulo nqui n'est rien d'autre que le point de départ du cycle. Ainsi, nous pouvons voir qu'après m étapes, elle arrive au début du cycle et la tortue l'y rencontrera car elle parcourra m étapes à partir du début de la liste chaînée.

En remarque, nous pouvons également calculer le temps de leur intersection de cette manière: la condition t = 0 modulo nnous dit qu'ils se rencontreront à un moment qui est un multiple de la longueur du cycle, et aussi t devrait être supérieur à m car ils se rencontreraient en le cycle . Le temps pris sera donc égal au premier multiple de n qui est supérieur à m .

Supposons que vos pointeurs se rencontrent à l'intersection des points y et z.

n et m sont les nombres de boucles les plus rapides et les plus lentes du pointeur respectivement avant la rencontre.

Reportez-vous à l'image pour le reste de la preuve. Trouver le point de départ de la boucle dans la liste chaînée