détecter le début d'une boucle dans un seul liés liste de liens?

J'ai entendu cette question exacte que d'une entrevue questionnaire.

La solution la plus élégante est:

Mettre les deux pointeurs au premier élément (appelons les A et B)

Puis continuer boucle::

• Avance à l'élément suivant
• Avance à l'élément suivant de nouveau
• Avance B à l'élément suivant

Chaque fois que vous mettez à jour un pointeur, vérifiez si A et B sont identiques.
Si, à un certain point de pointeurs A et B sont identiques, alors vous avez une boucle.
Le problème avec cette approche est que vous pouvez vous retrouver en mouvement autour de la boucle deux fois, mais pas plus de deux fois avec Un pointeur

Si vous voulez à réellement trouver l'élément qui a deux pointeurs pointant vers elle, ce qui est plus difficile. Je sortait d'une branche et dire que ses impossible de le faire avec seulement deux pointeurs, sauf si vous êtes prêt à répéter à la suite de la liste liée à un grand nombre de fois.

Le moyen le plus efficace de le faire avec plus de mémoire, serait de mettre les liens vers les éléments de la matrice et, à les trier, puis regarder pour une répétition.

PREUVE MATHÉMATIQUE + LA SOLUTION

Let 'k' be the number of steps from HEADER to BEGINLOOP.
Let 'm' be the number of steps from HEADER to MEETPOINT.
Let 'n' be the number of steps in the loop.
Also, consider two pointers 'P' and 'Q'. Q having 2x speed than P.

CAS SIMPLE: Lorsque k < N

Lorsque le pointeur " P " serait à BEGINLOOP (c'est à dire qu'il aurait voyagé 'k' étapes), Q aurait voyagé '2k' étapes. Oui, effectivement, Q est en avance de '2k-k = k', étapes de P lorsque P entre dans la boucle, et donc Q est 'n-k' pas derrière la BEGINLOOP maintenant.

Lorsque P aurait déplacé de BEGINLOOP à MEETPONT, il aurait voyagé "m-k' étapes. En ce moment, Q aurait voyagé '2(m-k)' étapes. Mais, depuis, ils ont rencontré, et Q commencé "n-k" pas derrière la BEGINLOOP, oui, effectivement,
'2(m-k) (n-k)' doit être égal à '(m-k)'
Donc,

=> 2m - 2k - n + k = m - k
=> 2m - n = m
=> n = m

QUI SIGNIFIE, P et Q satisfont au point égal au nombre d'étapes (ou plusieurs pour être général, voir le cas mentionné ci-dessous) dans la boucle. Maintenant, à la MEETPOINT, à la fois P et Q sont 'n-(m-k) les mesures prises par derrière, j'.e, 'k', pas derrière ,comme nous l'avons vu, n=m.
Donc, si nous commençons à P à partir de l'en-TÊTE de nouveau, et Q à partir de la MEETPOINT mais cette fois avec le rythme égal à P, P et Q seront désormais réunion à BEGINLOOP seulement.

CAS GÉNÉRAL: Dire, k = nX + Y, Y < n
(D'où, k%n = Y)

Lorsque le pointeur " P " serait à BEGINLOOP (c'est à dire qu'il aurait voyagé 'k' étapes), Q aurait voyagé '2k' étapes. Oui, effectivement, Q est en avance de '2k-k = k', étapes de P lorsque P entre dans la boucle. Mais, veuillez noter " k "est supérieure à "n", ce qui signifie Q aurait fait plusieurs tours de la boucle. Oui, effectivement, Q est 'n-(k%n)' pas derrière la BEGINLOOP maintenant.

Lorsque P aurait déplacé de BEGINLOOP à MEETPOINT, il aurait voyagé "m-k' étapes. (D'où, effectivement, MEETPOINT serait à l' "(m-k)%n' pas d'avance de BEGINLOOP maintenant.) En ce moment, Q aurait voyagé '2(m-k)' étapes. Mais, depuis, ils ont rencontré, et Q commencé 'n-(k%n)' pas derrière la BEGINLOOP, oui, effectivement, la nouvelle position de Q (qui est '(2(m-k) (n-k/%n)%n "de BEGINLOOP) doit être égale à la nouvelle position de P (qui est "(m-k)%n' depuis le début de la BOUCLE).

Donc,

=> (2(m - k) - (n - k%n))%n = (m - k)%n
=> (2(m - k) - (n - k%n))%n = m%n - k%n
=> (2(m - k) - (n - Y))%n = m%n - Y   (as k%n = Y)
=> 2m%n - 2k%n - n%n + Y%n = m%n - Y
=> 2m%n - Y - 0 + Y = m%n - Y    (Y%n = Y as Y < n)
=> m%n = 0
=> 'm' should be multiple of 'n'

Procéder de la manière habituelle, vous allez utiliser pour trouver la boucle. c'est à dire. Deux pointeurs, l'incrément de un en seule étape(slowPointer) et d'autres en deux étapes(fastPointer), Si elles remplissent toutes les deux dans un moment, il y a une boucle.

Comme vous pouvez l'avez déjà compris que le point de rencontre est k Étape avant que le chef de la boucle.

où k est la taille de la non-boucle partie de la liste.

maintenant, déplacez lent à la tête de la boucle

maintenir Rapide au point de collision

chacun d'entre eux sont k Étape depuis le début de la boucle (Lent du début de la liste où que rapide est k étape avant que le chef de la boucle - Dessiner l'image pour obtenir le plus de clarté)

Maintenant déplacer à la même vitesse - Ils doivent se rencontrer au début de la boucle

par exemple

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

Il y a deux façon de trouver des boucles dans une liste de liens.
1. L'utilisation de deux pointeur d'une avance d'un pas et autres avances de deux étapes, si il est en boucle, dans un moment, les deux pointeur obtenir la même valeur et ne jamais atteindre la valeur null. Mais si il n'y a pas de boucle de pointeur atteint nulle en un point et deux pointeur de ne jamais obtenir la même valeur. Mais dans cette approche, nous pouvons obtenir il y a une boucle dans le lien de la liste, mais nous ne pouvons pas dire où exactement le démarrage de la boucle. Ce n'est pas le moyen efficace ainsi.

1. Utiliser une fonction de hachage d'une manière telle que la valeur doit être unique. Emballent si nous essayons d'insérer le double il doit par le biais de l'exception. Puis voyage à travers chaque nœud et de pousser l'adresse dans la table de hachage. Si le pointeur de parvenir à null et pas d'exception à partir de la table de hachage n'y a pas de cycle dans le lien de la liste. Si nous obtenons aucune exception de hachage signifie qu'il y a un cycle dans la liste et qui est le lien à partir duquel le cycle commence.

La meilleure réponse que j'ai trouvé est ici:

tianrunhe: trouvez-boucle-point de départ-dans-un-circulaire-liste liée

• 'm' étant la distance entre la TÊTE et le START_LOOP
• "L" étant la longueur de la boucle
• "d" étant la distance entre MEETING_POINT et START_LOOP

• p1 déplace à V, et p2 se déplaçant à 2*V

  lorsque les 2 pointeurs de répondre: distance parcourue est de = m+ n*L-d = 2*(m+ L-d)

  => ce qui signifie (pas mathematicaly démontré ici) que si p1 commence à partir de la TÊTE & p2 commence à partir de MEETING_POINT & ils se déplacent à la même vitesse, ils vont rencontrer @ START_LOOP

1. Procéder de la manière habituelle, vous allez utiliser pour trouver la boucle. c'est à dire. Deux pointeurs, l'incrément de un en seule étape et d'autres en deux étapes, Si elles remplissent toutes les deux dans un moment, il y a une boucle.

2. Conserver l'un des pointeurs fixes obtenir le nombre total de nœuds dans la boucle de dire L.

3. Maintenant à partir de ce point(incrément deuxième pointeur vers le nœud suivant dans la boucle) dans la boucle inverse de la liste, et de compter le nombre de nœuds traversés, dire X.

4. Maintenant, en utilisant la deuxième pointeur(la boucle est cassé) à partir du même point dans la boucle travrse la liste, et de compter le nombre de nœuds restants dire Y

5. La boucle commence après la ((X+Y)-L)\2 nœuds. Ou il commence à l' (((X+Y)-L)\2+1)ème nœud.

void loopstartpoint(Node head){
    Node slow = head.next;;
    Node fast = head.next.next;

    while(fast!=null && fast.next!=null){
        slow = slow.next;
        fast = fast.next.next;

        if(slow==fast){
            System.out.println("Detected loop ");
            break;
        }
    }

    slow=head;
    while(slow!=fast){
        slow= slow.next;
        fast = fast.next;
    }
    System.out.println("Starting position of loop is "+slow.data);
}