détecter le début d'une boucle dans une liste de liens seuls lié?

Question

Y at-il moyen de trouver le début d'une boucle dans une liste de lien en utilisant pas plus de deux pointeurs? Je ne veux pas visiter chaque nœud et marquer vu et des rapports du premier noeud déjà été seen.Is il une autre façon de le faire?

Answer 1

Je l'ai entendu cette question exactement comme question quiz entrevue.

La solution la plus élégante est:

Placez les deux pointeurs au premier élément (les appeler A et B)

Alors continuez en boucle ::

    
• A l'avance à l'autre élément     
• A l'avance à l'autre élément nouveau     
• Advance B à l'autre élément

Chaque fois que vous mettez à jour un pointeur, vérifiez si A et B sont identiques. Si à certains pointeurs de points A et B sont identiques, alors vous avez une boucle. Problème avec cette approche est que vous pouvez finir par se déplacer autour de la boucle deux fois, mais pas plus que deux fois avec pointeur A

Si vous voulez réellement trouver l'élément qui a deux pointeurs pointant vers elle, qui est plus difficile. Je sors d'un membre et dire qu'il soit impossible de le faire avec seulement deux pointeurs à moins que vous êtes prêt à répéter après la liste chaînée un grand nombre de fois.

La façon la plus efficace de le faire avec plus de mémoire, serait de mettre les pointeurs vers les éléments et tableau, le tri, et ensuite chercher une répétition.

Answer 2

Etape 1: Procédez de la manière habituelle, vous utiliserez pour trouver la boucle, à savoir Avoir deux pointeurs, incrémenter un à l'étape unique et d'autres en deux étapes, Si les deux se rencontrent dans un certain temps, il y a une boucle.

Etape 2: Gel d'un pointeur où il était et incrémenter l'autre pointeur en une seule étape en comptant les étapes que vous faites et quand les deux se rencontrent à nouveau, le compte vous donnera la longueur de la boucle (cette est identique à compter le nombre d'éléments dans une liste de lien circulaire).

Etape 3: Réinitialiser les deux pointeurs au début de la liste de liens, incrémenter un pointeur sur la longueur des temps de boucle, puis démarrer le deuxième pointeur. incrémenter les deux pointeurs en une seule étape et quand ils se rencontrent à nouveau, ce sera le début de la boucle (c'est le même que trouver le n ^e élément de la fin de la liste des liens).

Answer 3

+ MATHÉMATIQUES PROOF 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.

CASE simple: lorsque k

Lorsque le pointeur « P » serait à BeginLoop (à savoir qu'il aurait parcouru étapes « K »), Q aurait parcouru étapes « 2k ». Donc, en fait, Q est en avance d'étapes '2k-k = k' de P lorsque P entre dans la boucle et, par conséquent, Q est 'n-k' pas derrière le BeginLoop maintenant.

P serait déplacé de BeginLoop à MEETPONT, il aurait parcouru étapes « m-k ». En ce moment, Q aurait parcouru '2 (m-k)' étapes. Mais, depuis leur rencontre, et Q ont commencé 'n-k pas derrière la BeginLoop, donc, effectivement, '2 (m-k) - (n-k)' doit être égal à (m-k) ' Ainsi,

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

Cela signifie que, rencontrent P et Q au niveau du point correspondant au nombre d'étapes (ou multiple pour être général, voir le cas mentionné ci-dessous) dans la boucle. Or, au MEETPOINT, à la fois P et Q sont 'N- (m-k)' étapes derrière, i.e., les étapes 'k' derrière, comme on l'a vu n = m. Donc, si nous commençons P de nouveau HEADER et Q de la MEETPOINT mais cette fois avec le rythme égal à P, P et Q sera maintenant réunirons à BeginLoop seulement.

Cas général: Say, k = nX + Y, Y (Par conséquent, k% n = Y)

Lorsque le pointeur « P » serait à BeginLoop (à savoir qu'il aurait parcouru étapes « K »), Q aurait parcouru étapes « 2k ». Donc, en fait, Q est en avance d'étapes « 2k-k = k » de P lorsque P entre dans la boucle. Mais, s'il vous plaît noter « k » est supérieur à « n », ce qui signifie Q aurait fait plusieurs tours de la boucle. Donc, en fait, Q est 'n- (k)% n' pas derrière le BeginLoop maintenant.

P serait déplacé de BeginLoop à MEETPOINT, il aurait parcouru étapes « m-k ». (Par conséquent, efficacement, MEETPOINT serait à '(m-k)% n' pas devant BeginLoop maintenant.) En ce temps, Q aurait parcouru '2 (m-k)' étapes. Mais, depuis leur rencontre, et Q ont commencé 'n (k% n)' pas derrière la BeginLoop, donc, effectivement, nouvelle position de Q (qui est « (2 (mk) - (nk /% n))% n 'de BeginLoop) doit être égale à la nouvelle position P (ce qui est '(mk)% n' à partir du début LOOP).

=> (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'

Answer 4

D'abord, nous essayons de savoir, est-il une boucle dans la liste ou non. Si la boucle existe alors nous essayons de trouver le point de départ de la boucle. Pour cela, nous utilisons deux pointeurs à savoir slowPtr et fastPtr. Dans la première détection (vérification de la boucle), fastPtr déplace deux étapes en une seule fois, mais slowPtr se déplace d'un pas en avant à la fois.

slowPtr   1   2   3   4   5   6   7
fastPtr   1   3   5   7   9   5   7

Il est clair que s'il y a une boucle dans la liste puis ils se réuniront au point (point 7 image ci-dessus), car le pointeur fastPtr est en cours d'exécution d'autre deux fois plus rapide.

Maintenant, nous arrivons à la deuxième problème de trouver le point de départ de la boucle.

Supposons, ils se rencontrent au point 7 (tel que mentionné dans l'image ci-dessus). Ensuite, slowPtr sort de la boucle et se au début de la liste signifie au point 1, mais fastPtr encore au point de rencontre (point 7). Maintenant, nous comparons à la fois la valeur des pointeurs, si elles mêmes, alors il est le point de départ de la boucle sinon, nous passons une étape à l'avance (ici fastPtr se déplace également d'un pas à chaque fois) et comparer à nouveau jusqu'à ce que nous trouvons même point.

slowPtr   1   2   3   4
fastPtr   7   8   9   4

Maintenant une question vient à l'esprit, comment est-il possible. Donc, il y a une bonne preuve mathématique.

Supposons que:

m => length from starting of list to starting of loop (i.e 1-2-3-4)
l => length of loop (i.e. 4-5-6-7-8-9)
k => length between starting of loop to meeting point (i.e. 4-5-6-7)

Total distance traveled by slowPtr = m + p(l) +k
where p => number of repetition of circle covered by slowPtr

Total distance traveled by fastPtr = m + q(l) + k
where q => number of repetition of circle covered by fastPtr

Since,
fastPtr running twice faster than slowPtr

Hence,
Total distance traveled by fastPtr = 2 X Total distance traveled by slowPtr
i.e
m + q(l) + k = 2 * ( m + p(l) +k )
or, m + k = q(l) - p(l)
or, m + k = (q-p) l
or, m = (q-p) l - k

So,
If slowPtr starts from beginning of list and travels "m" length then, it will reach to Point 4 (i.e. 1-2-3-4)

and
fastPtr start from Point 7 and travels " (q-p) l - k " length then, it will reach to Point 4 (i.e. 7-8-9-4),
because "(q-p) l" is a complete circle length with " (q-p) " times.

Plus détail ici

Answer 5

Procédez de la manière habituelle que vous utiliserez pour trouver la boucle. c'est à dire. Avoir deux pointeurs, incrémenter un à l'étape unique (slowPointer) et d'autres en deux étapes (fastPointer), Si les deux se rencontrent dans quelque temps, il y a une boucle.

Comme vous pouvez l'auriez déjà réalisé ce point de rencontre est k étape avant que la tête de la boucle.

k étant la taille de la partie non bouclée de la liste.

maintenant passer du temps à la tête de la boucle

au point rapide garder collision

chacun d'entre eux sont k pas du départ de la boucle (lente du début de la liste où est aussi rapide étape k avant que la tête du boucle- Dessiner l'image pour obtenir la clarté)

Maintenant, les déplacer à la même vitesse - Ils doivent se réunir au début de la boucle

par exemple

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

Answer 6

est un code pour trouver début de boucle dans la liste chaînée:

public static void findStartOfLoop(Node n) {

    Node fast, slow;
    fast = slow = n;
    do {
        fast = fast.next.next;
        slow = slow.next;
    } while (fast != slow);       

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

    System.out.println(" Start of Loop : " + fast.v);
}

Answer 7

Il y a deux façons de trouver les boucles dans une liste de liens. 1. Utilisez deux pointeur d'une avance d'un pas et autre avance deux étapes s'il y a boucle, les deux pointeur de la même valeur en un point et ne jamais atteindre null. Mais s'il n'y a pas de pointeur de boucle atteint null en un point et deux pointeur jamais la même valeur. Mais dans cette approche, nous pouvons y arriver est une boucle dans la liste de liens, mais nous ne pouvons pas dire où exactement à partir de la boucle. Ce n'est pas la manière efficace aussi bien.

2. Utilisez une fonction de hachage de telle sorte que la valeur doit être unique. Incase si nous essayons d'insérer le double il se doit par l'exception. Voyage ensuite à travers chaque nœud et pousser l'adresse dans le hachage. Si la portée de pointeur NULL et aucune exception du moyen de hachage il n'y a pas de cycle dans la liste de liens. Si nous obtenons une exception de hachage signifie qu'il ya un cycle dans la liste et qui est le lien à partir duquel le cycle commence.

Answer 8

Eh bien, j'essayé d'une manière en utilisant un pointeur ... J'ai essayé la méthode dans plusieurs ensembles de données .... Comme la mémoire pour chacun des noeuds d'une liste chaînée sont attribués dans un ordre croissant, donc en traversant la liste chaînée de la tête de la liste liée, si l'adresse d'un noeud devient plus grande que l'adresse du nœud il pointe, nous pouvons déterminer il y a une boucle, ainsi que l'élément de début de la boucle.

Answer 9

La meilleure réponse que j'ai trouvé était ici:
tianrunhe: Rechercher- boucle de point de départ-in-a-lié-circulaire liste

• 'm' étant la distance entre la tête et start_loop
• 'L' étant une longueur de boucle
• 'd' étant la distance entre MEETING_POINT et start_loop

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

  2 lorsque le pointeur se rencontrent: distance parcourue est = m + n * L -d = 2 * (m + L -d)   

    => Ce qui signifie (non démontré ici mathématiquement) que si p1 commence à partir HEAD & p2 commence à partir MEETING_POINT et ils se déplacent au même rythme, ils rencontreront @ start_loop

Answer 10

Reportez-vous à ce lien pour réponse complète.

Answer 11

1. Procédez de la manière habituelle que vous utiliserez pour trouver la boucle. c'est à dire. Avoir deux pointeurs, incrémenter un à l'étape unique et d'autres en deux étapes, Si les deux se rencontrent dans un certain temps, il y a une boucle.

2. Gardez l'un des pointeurs fixes obtenir le nombre total de noeuds dans la boucle dire L.

3. Maintenant, à partir de ce point (incrément deuxième pointeur vers le noeud suivant dans la boucle) dans la boucle inverser la liste liée et de compter le nombre de noeuds traversés, par exemple X.

4. Maintenant, en utilisant le second pointeur (boucle est rompue) à partir du même point dans la boucle travrse la liste liée et de compter le nombre de noeuds restants dire Y

5. La boucle commence après le (-L (X + Y)) \ 2 noeuds. Or, il commence à la (((X + Y) -L) \ 2 + 1) ième noeud.

Answer 12

1. Procédez de la manière habituelle que vous utiliserez pour trouver la boucle. c'est à dire. Avoir deux pointeurs, incrémenter un à l'étape unique et d'autres en deux étapes, si les deux se rencontrent dans quelque temps, il y a une boucle.

2. Gardez l'un des pointeurs fixes obtenir le nombre total de noeuds dans la boucle dire L.

3. Maintenant, à partir de ce point (incrément deuxième pointeur vers le noeud suivant dans la boucle) dans la boucle inverser la liste liée et de compter le nombre de noeuds traversés, par exemple X.

4. Maintenant, en utilisant le second pointeur (boucle est rompue) à partir du même point dans la boucle travrse la liste liée et de compter le nombre de noeuds restants dire Y

5. La boucle commence après le (-L (X + Y)) \ 2 noeuds. Or, il commence à la (((X + Y) -L) \ 2 + 1) ième noeud.

Answer 13

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

Answer 14

1. détecter boucle
2. copier l'adresse de chaque élément en jeu. Si double se trouve c'est le début de la boucle