Interview: Supprimer la boucle dans la liste des liens – Java

On m’a posé cette question dans l’interview: “Comment détecter la boucle dans la liste liée?”, J’ai résolu ce problème mais immédiatement l’intervieweur m’a demandé comment supprimer la boucle dans une liste chaînée. J’ai tâtonné

Donc, tout pointeur sur la façon de résoudre ce problème peut être un pseudo-code ou une définition de méthode?

Je suis à l’aise avec Java alors j’ai tagué cette question sous Java.

Pour l’instance cette liste liée a une boucle

0--->1---->2---->3---->4---->5---->6 ▲ | | ▼ 11<—-22<—-12<—-9<—-8 

    Ce problème comporte deux parties:

    1. Détecter s’il y a une boucle dans la liste
    2. Identifier le début de la boucle

    Une fois que vous savez où la boucle démarre, il est facile d’identifier le dernier élément de la liste car c’est l’élément de la liste qui suit le début de la boucle et qui retourne au début de la boucle. Il est alors sortingvial de mettre le prochain pointeur / référence de cet élément à null pour corriger la liste de liens cycliques (pas la liste chaînée circulaire qui est l’endroit où les derniers éléments pointent vers le premier – ce serait une instance spécifique de listes cycliques).

    1. L’algorithme de détection de cycle de Floyd, également appelé algorithme de la tortue et du lièvre car il implique l’utilisation de deux pointeurs / références qui se déplacent à des vitesses différentes, est une façon de détecter le cycle. S’il y a un cycle, les deux pointeurs (disons p1 et p2 ) finiront par pointer vers le même élément après un nombre fini d’étapes. Fait intéressant, il peut être prouvé que l’élément auquel ils se rencontrent aura la même distance au début de la boucle (en continuant de parcourir la liste dans le même sens) que le début de la boucle est en tête de la liste. . Autrement dit, si la partie linéaire de la liste a k éléments, les deux pointeurs se rencontreront à l’intérieur de la boucle de longueur m en un point mk du début de la boucle ou k éléments jusqu’à la fin de la boucle (bien sûr, c’est une boucle donc il n’y a pas de «fin» – c’est juste le «départ» encore une fois. Et cela nous donne un moyen de trouver le début de la boucle:

    2. Une fois qu’un cycle a été détecté, laissez p2 continuer à pointer vers l’élément où la boucle pour l’étape ci-dessus s’est terminée mais réinitialisez p1 pour qu’il pointe en tête de la liste. Maintenant, déplacez chaque pointeur un élément à la fois. Puisque p2 commencé à l’intérieur de la boucle, il continuera à boucler. Après k étapes (égale à la distance du début de la boucle à partir de la tête de la liste), p1 et p2 se rencontreront à nouveau. Cela vous donnera une référence au début de la boucle.

    3. Il est maintenant facile de définir p1 (ou p2 ) pour pointer sur l’élément commençant la boucle et parcourir la boucle jusqu’à ce que p1 pointe vers l’élément de départ. À ce stade, p1 fait référence à la liste des derniers éléments et son prochain pointeur peut être défini sur null .


    Voici un code Java rapide et sale supposant une liste de Node liés où un Node a une référence next . Cela pourrait être optimisé mais cela devrait vous donner l’idée de base:

     Node slow, fast, start; fast = slow = head; //PART I - Detect if a loop exists while (true) { // fast will always fall off the end of the list if it is linear if (fast == null || fast.next == null) { // no loop return; } else if (fast == slow || fast.next == slow) { // detected a loop break; } else { fast = fast.next.next; // move 2 nodes at at time slow = slow.next; // move 1 node at a time } } //PART II - Identify the node that is the start of the loop fast = head; //reset one of the references to head of list //until both the references are one short of the common element which is the start of the loop while(fast.next != slow.next) { fast = fast.next; slow = slow.next; } start = fast.next; //PART III - Eliminate the loop by setting the 'next' pointer //of the last element to null fast = start; while(fast.next != start) { fast = fast.next; } fast.next = null; //break the loop 

    Cette explication pourrait aider le pourquoi derrière la partie II:

    Supposons que la longueur du cycle est M et que la longueur du rest de la liste chaînée soit L. Déterminons quelle est la position dans le cycle lorsque t1 / t2 se rencontrent pour la première fois?

    Définir le premier noeud du cycle est la position 0, en suivant les liens que nous avons les positions 1, 2, …, jusqu’à M-1. (quand nous marchons dans le cycle, notre position actuelle est (walk_length) mod M, right?) Supposons que t1 / t2 se rencontrent d’abord à la position p, alors leur temps de parcours est le même, (L + k1 * M + p) / v = (L + k2 * M + p) / 2v pour certains k1

    Donc, il conclut que si t1 commence à partir de p, t2 part de la tête et se déplace à la même vitesse, puis va se rencontrer à la position 0, le premier nœud du cycle. QED.

    Plus de références:

    • http://www.quora.com/How-does-Floyds-cycle-finding-algorithm-work
    • Expliquez comment le fonctionnement du nœud de démarrage du cycle dans le cycle lié à la liste fonctionne?
    • Preuve de détection du début de cycle dans la liste chaînée
    • La réponse de Hristo à cette question sur cette page cite également une explication tirée d’un livre d’entretiens

    Solution 1 – gracieuseté de Career Cup et du livre “Cracking the Coding Interview” :

     public static LinkedListNode findStartOfLoop(LinkedListNode head) { LinkedListNode n1 = head; LinkedListNode n2 = head; // find meeting point using Tortoise and Hare algorithm // this is just Floyd's cycle detection algorithm while (n2.next != null) { n1 = n1.next; n2 = n2.next.next; if (n1 == n2) { break; } } // Error check - there is no meeting point, and therefore no loop if (n2.next == null) { return null; } /* Move n1 to Head. Keep n2 at Meeting Point. Each are k steps /* from the Loop Start. If they move at the same pace, they must * meet at Loop Start. */ n1 = head; while (n1 != n2) { n1 = n1.next; n2 = n2.next; } // Now n2 points to the start of the loop. return n2; } 

    L’explication de cette solution provient directement du livre:

    Si nous déplaçons deux pointeurs, l’un avec la vitesse 1 et l’autre avec la vitesse 2, ils se retrouveront si la liste des liens a une boucle. Pourquoi? Pensez à deux voitures conduisant sur une piste; la voiture la plus rapide passera toujours la plus lente!

    La partie délicate ici consiste à trouver le début de la boucle. Imaginez, par analogie, deux personnes qui courent autour d’une piste, l’une courant deux fois plus vite que l’autre. S’ils commencent au même endroit, quand se réuniront-ils ensuite? Ils se rencontreront ensuite au début du tour suivant.

    Maintenant, supposons que Fast Runner ait une longueur d’avance de k mètres sur un tour de pas. Quand vont-ils se rencontrer ensuite? Ils se rencontreront k mètres avant le début du tour suivant. (Pourquoi? Fast Runner aurait fait k + 2 (n – k) pas, y compris son début de partie, et Slow Runner aurait fait n – k étapes. Les deux étapes seraient k avant le début de la boucle).

    Maintenant, pour revenir au problème, lorsque Fast Runner (n2) et Slow Runner (n1) se déplacent autour de notre liste chaînée circulaire, n2 aura une longueur d’avance sur la boucle lorsque n1 entrera. Plus précisément, il aura un début de tête de k, où k est le nombre de nœuds avant la boucle. Puisque n2 a un début de tête de k nœuds, n1 et n2 rencontreront k nœuds avant le début de la boucle.

    Donc, nous soaps maintenant ce qui suit:

    1. Head is k nodes de LoopStart (par définition)
    2. MeetingPoint pour n1 et n2 est k nœuds de LoopStart (comme indiqué ci-dessus)

    Ainsi, si nous revenons à n1 et gardons n2 à MeetingPoint, et les déplacons tous deux au même rythme, ils se rencontreront à LoopStart

    Solution 2 – courtoisie de ma part 🙂

     public static LinkedListNode findHeadOfLoop(LinkedListNode head) { int indexer = 0; Map map = new IdentityHashMap(); map.put(head, indexer); indexer++; // start walking along the list while putting each node in the HashMap // if we come to a node that is already in the list, // then that node is the start of the cycle LinkedListNode curr = head; while (curr != null) { if (map.containsKey(curr.next)) { curr = curr.next; break; } curr = curr.next; map.put(curr, indexer); indexer++; } return curr; } 

    J’espère que ça aide.
    Hristo

    Cette réponse n’est pas destinée à concurrencer pour la réponse, mais plutôt à expliquer un peu plus la réunion des deux nœuds dans l’algorithme de la tortue et du lièvre.

    1. Les deux nœuds finiront par entrer dans la boucle. Parce que l’un se déplace plus vite (F) que l’autre (S), (F) finira par tourner (S).

    2. Si le début de la boucle se trouve à la tête de la liste, (F) doit répondre (S) à la tête de la liste. C’est UNIQUEMENT parce que la vitesse de (F) est de 2X (S); si c’était 3X cela ne serait pas vrai. Ceci est vrai parce que (F) effectue un tour quand (S) termine un demi-tour, donc quand (S) termine son premier tour, (F) a complété deux tours – et est de retour au début de la boucle avec (S) .

    3. Si le début de la boucle n’est PAS à la tête de la liste, alors (S) entre dans la boucle, (F) a un début de tête de (k) nœuds dans la boucle. Comme la vitesse de (S) n’est qu’un nœud à la fois, elle rencontrera (F) à (k) nœuds du début de la boucle – comme dans (k) plus d’étapes avant d’atteindre les étapes de démarrage, NOT (k) le début. Cela ne serait PAS vrai si la vitesse de (S) n’était pas un et que le rapport de vitesse n’était pas 2: 1 entre (F) et (S).

      3.1. C’est là que ça devient un peu difficile à expliquer. Nous pouvons convenir que (F) continuera à battre (S) jusqu’à ce qu’ils se rencontrent (voir 1 ci-dessus), mais pourquoi (k) les nœuds du début de la boucle? Considérons l’équation suivante où M est le nombre de nœuds ou la distance de la boucle et k est le début de la tête (F); l’équation représente la distance parcourue par (F) en fonction du temps t à gauche en termes de distance parcourue par (S) à droite:

      d_F (t) = 2 * d_S (t) + k

      Donc, quand (S) entre dans la boucle et a parcouru 0 distance dans la boucle, (F) n’a parcouru que la distance (k). Au temps d_S = M – k, d_F = 2M – k. Comme nous devons également utiliser des calculs modulaires en tenant compte du fait que M représente la distance totale d’un tour dans la boucle, la POSITION de (F) et (S) à tout instant M (aucun rest) est 0. Donc, en termes de POSITION (ou le différentiel), cela laisse k (ou plutôt, -k).

      Et ainsi, finalement, (S) et (F) se rencontreront à des positions (0 – k) ou (k) des nœuds éloignés du début de la boucle.

    4. Compte tenu de [3] ci-dessus, comme (k) représente le début de course (F) et que (F) a parcouru 2 fois la distance (S) parcourue pour entrer dans la boucle en tête de liste, (k) représente également distance depuis le début de la liste, qui représente alors le début de la boucle.

    C’est un peu tard, alors j’espère que je me suis articulé efficacement. Faites-moi savoir autrement et je vais essayer de mettre à jour ma réponse.

    Si l’utilisation d’une carte de hachage d’identité ( IdentityHashMap, par exemple ) est autorisée, cela est extrêmement facile à résoudre. Il utilise cependant plus d’espace.

    Parcourez la liste des noeuds. Pour chaque nœud rencontré, ajoutez-le à la carte d’identité. Si le nœud existait déjà dans la carte d’identité, alors la liste a un lien circulaire et le nœud qui était antérieur à ce conflit est connu (vérifiez avant de déplacer ou conservez le “dernier nœud”). rompre le cycle.

    Suivre cette approche simple devrait être un exercice amusant: le code rest un exercice pour le lecteur.

    Heureux codage

      0--->1---->2---->3---->4---->5---->6 ▲ | | ▼ 11<—-22<—-12<—-9<—-8 

    Insérez un nœud factice après chaque nœud de la liste de liens et, avant d'insérer, vérifiez que le nœud suivant est factice ou non. Si à côté de la prochaine est factice, insérez null dans à côté de ce nœud.

      0-->D->1-->D->2-->D->3->D-->4->D-->5->D-->6 ▲ | / ▼ 11<—D<-22<—D<-12<—D<-9<—D<--8 Node(11)->next->next == D Node(11)->next =null 
     //Find a Loop in Linked List and remove link between node public void findLoopInList() { Node fastNode = head; Node slowNode = head; boolean isLoopExist = false; while (slowNode != null && fastNode != null && fastNode.next != null) { fastNode = fastNode.next.next; slowNode = slowNode.next; if (slowNode == fastNode) { System.out.print("\n Loop Found"); isLoopExist = true; break; } } if (isLoopExist) { slowNode = head; Node prevNode = null; while (slowNode != fastNode) { prevNode = fastNode; fastNode = fastNode.next; slowNode = slowNode.next; } System.out.print("Loop Found Node : " + slowNode.mData); prevNode.next = null; } } 

    🙂 GlbMP