Interview: Supprimer la boucle dans la liste chaînée - Java

Question

J'ai été posé cette question en entretien: "Comment détecter la boucle dans une liste chaînée?", J'ai résolu cela mais immédiatement l'intervieweur m'a demandé comment enlever la boucle dans une liste chaînée. J'ai bafouillé.

Alors des indications sur comment résoudre cela, peut-être du pseudo-code, ou une définition de méthode?

Je suis à l'aise avec Java donc j'ai marqué cette question sous java.

Par exemple cette liste chaînée a une boucle

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

Answer 1

Il y a deux parties à ce problème :

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ù commence la boucle, il est facile d'identifier le dernier élément de la liste car c'est l'élément de la liste suivant le début de la boucle qui finit par pointer à nouveau vers le début de la boucle. Il est alors trivial de définir le pointeur/référence suivant de cet élément à null pour corriger la liste de liens cycliques (pas la liste liée circulaire où les derniers éléments pointent vers le premier - ce serait une instance spécifique des listes cycliques).

1. L'algorithme de détection de cycle de Floyd, aussi appelé algorithme du lièvre et de la tortue 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. Il est intéressant de noter qu'il peut être prouvé que l'élément où ils se rencontrent sera à la même distance du début de la boucle (continuant à traverser la liste dans la même direction avant) que le début de la boucle est au début 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 à un point m-k du début de la boucle ou k éléments de 'l'extrémité' de la boucle (bien sûr, c'est une boucle donc elle n'a pas de 'fin' - c'est simplement le 'début' une fois de plus). 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 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 à nouveau vers le début de la liste. Déplacez ensuite chaque pointeur un élément à la fois. Comme p2 a commencé à l'intérieur de la boucle, il continuera à boucler. Après k étapes (équivalent à la distance du début de la boucle du début de la liste), p1 et p2 se retrouveront à 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 vers l'élément démarrant la boucle et de traverser la boucle jusqu'à ce que p1 finisse par pointer à nouveau vers l'élément de démarrage. À ce stade, p1 référence le dernier' élément liste et son pointeur suivant peut être défini à null.

---

Voici un code Java rapide et sale en supposant une liste chaînée de Nœuds où un Nœud a une référence suivant. Cela pourrait être optimisé mais cela devrait vous donner une idée de base :

Nœud lent, rapide, début;
rapide = lent = tête;

//PARTIE I - Détecter si une boucle existe
while (true)
{
    // rapide tombera toujours de la fin de la liste s'il est linéaire
    if (rapide == null || rapide.suivant == null)
    {
        // pas de boucle
        return;
    }
    else if (rapide == lent || rapide.suivant == lent)
    {
        // boucle détectée
        break;
    }
    else
    {
        rapide = rapide.suivant.suivant; // déplacer 2 nœuds à la fois
        lent = lent.suivant; // déplacer 1 nœud à la fois
    }
}

//PARTIE II - Identifier le nœud qui est le début de la boucle
rapide = tête; //réinitialiser une des références à la tête de la liste

//jusqu'à ce que les deux références soient à un de l'élément commun qui est le début de la boucle
tant que(rapide.suivant != lent.suivant) 
{
    rapide = rapide.suivant;
    lent = lent.suivant;
}

début = rapide.suivant;

//PARTIE III - Éliminer la boucle en définissant le pointeur 'suivant' 
//de l'élément dernier à null
rapide = début;
tant que(rapide.suivant != début)
{
    rapide = rapide.suivant;
}

rapide.suivant = null; //casser la boucle

---

Cette explication pourrait aider à comprendre pourquoi la partie II :

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

Définissez le premier nœud dans le cycle comme étant la position 0, en suivant les liens nous avons les positions 1, 2,..., jusqu'à M-1. ( quand nous marchons dans le cycle, notre position actuelle est (longueur_marche) mod M, n'est-ce pas ?) Supposons que t1/t2 se rencontrent pour la première fois en position p, alors leur temps de trajet est le même, (L+k1*M+p)/v = (L+k2*M+p)/2v pour certains k1

Il en résulte que si t1 commence à p, t2 commence à la tête et se déplace à la même vitesse, alors s'assureront de se rencontrer en 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 fonctionne l'algorithme de recherche du nœud de départ du cycle dans une liste liée cyclique ?
• Preuve de la détection du début du cycle dans la liste chaînée
• La réponse de Hristo à cette question sur cette page cite également une explication d'un livre d'entretiens

Answer 2

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; 

    // trouver le point de rencontre en utilisant l'algorithme de la tortue et du lièvre
    // c'est simplement l'algorithme de détection de cycle de Floyd
    while (n2.next != null) { 
        n1 = n1.next; 
        n2 = n2.next.next; 
        if (n1 == n2) { 
            break; 
        }
    }

    // Vérification d'erreur - il n'y a pas de point de rencontre, donc pas de boucle
    if (n2.next == null) {
        return null;
    }

    /* Déplacer n1 à Head. Garder n2 au point de rencontre. Chacun est k pas
    de la boucle. S'ils se déplacent à la même vitesse, ils doivent nécessairement
     se rencontrer au début de la boucle. */
    n1 = head; 
    while (n1 != n2) { 
        n1 = n1.next; 
        n2 = n2.next; 
    }
    // Maintenant, n2 pointe vers le début de la boucle.
    return n2;
}

L'explication de cette solution vient directement du livre :

Si nous déplaçons deux pointeurs, l'un avec vitesse 1 et un autre avec vitesse 2, ils finiront par se rencontrer si la liste chaînée a une boucle. Pourquoi ? Pensez à deux voitures roulant sur une piste : la voiture la plus rapide passera toujours devant la plus lente !

La partie délicate ici est de trouver le début de la boucle. Imaginez, par analogie, deux personnes courir autour d'une piste, l'une courant deux fois plus vite que l'autre. S'ils commencent au même endroit, quand se rencontreront-ils ? Ils se rencontreront au début du prochain tour.

Maintenant, supposons que le coureur rapide ait une longueur d'avance de k mètres sur un tour de n étapes. Quand se rencontreront-ils la prochaine fois ? Ils se rencontreront k mètres avant le début du prochain tour. (Pourquoi ? Le coureur rapide aura fait k + 2(n - k) pas, comprenant son avance, et le coureur lent aura fait n - k pas. Les deux seront à k pas avant le début de la boucle.)

Maintenant, revenant au problème, lorsque le coureur rapide (n2) et le coureur lent (n1) se déplacent autour de notre liste chaînée circulaire, n2 aura un avantage de départ sur la boucle lorsque n1 entre. Spécifiquement, il aura un avantage de k, où k est le nombre de nœuds avant la boucle. Puisque n2 a un avantage de k nœuds, n1 et n2 se rencontreront k nœuds avant le début de la boucle.

Nous savons maintenant ce qui suit :

1. La tête est k noeuds du début de la boucle (par définition)
2. Le point de rencontre pour n1 et n2 est k noeuds du début de la boucle (comme montré ci-dessus)

Ainsi, si nous ramenons n1 à la tête et gardons n2 au point de rencontre, et les déplaçons tous les deux à la même vitesse, ils se rencontreront au début de la boucle

Solution 2 - gracieuseté de moi :)

public static LinkedListNode findHeadOfLoop(LinkedListNode head) {

    int indexeur = 0;
    Map map = new IdentityHashMap();
    map.put(head, indexeur);
    indexeur++;

    // commence à parcourir la liste tout en plaçant chaque nœud dans la HashMap
    // si nous arrivons à un nœud qui est déjà dans la liste,
    // alors ce nœud est le début du cycle
    LinkedListNode curr = head;
    while (curr != null) {

        if (map.containsKey(curr.next)) {
            curr = curr.next;
            break;
        }
        curr = curr.next;
        map.put(curr, indexeur);
        indexeur++;
    }
    return curr;
}

J'espère que cela vous aidera.
Hristo

Answer 3

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

1. Les deux nœuds entreront éventuellement dans la boucle. Parce que l'un se déplace plus rapidement (F) que l'autre (S), (F) finira par dépasser (S).

2. Si le début de la boucle est à la tête de la liste, (F) doit retrouver (S) à la tête de la liste. Cela est VRAIEMENT dû au fait que la vitesse de (F) est 2X celle de (S); si c'était 3X, cela ne serait pas vrai. Cela est vrai car (F) termine un tour quand (S) en termine la moitié, donc quand (S) termine son premier tour, (F) a terminé 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 au moment où (S) entre dans la boucle, (F) a pris de l'avance de (k) nœuds dans la boucle. Parce que la vitesse de (S) est d'un seul nœud à la fois, il retrouvera (F) à (k) nœuds du début de la boucle - c'est-à-dire, (k) étapes de plus avant d'atteindre le début, PAS (k) étapes APRÈS le début. Cela ne serait pas vrai si la vitesse de (S) n'était pas d'un seul nœud à la fois et si le ratio de vitesse n'était pas de 2:1 entre (F) et (S).

   3.1. C'est ici que cela devient un peu difficile à expliquer. Nous sommes d'accord pour dire que (F) continuera à dépasser (S) jusqu'à ce qu'ils se retrouvent finalement (voir 1 ci-dessus), mais pourquoi à (k) nœuds du début de la boucle? Considérez l'équation suivante où M est le nombre de nœuds ou la distance de la boucle et k est l'avance (k) que (F) avait; l'équation représente la distance parcourue par (F) en fonction du temps t à gauche par rapport à la 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) a parcouru seulement la distance (k). Au moment où d_S = M - k, d_F = 2M - k. Comme nous devons également utiliser des mathématiques modulaires en prenant en compte que M représente la distance totale d'un seul tour dans la boucle, la POSITION de (F) et (S) à tout M entier (sans reste) est 0. Donc ensuite, en termes de POSITION (ou de différentiel), cela laisse k (ou plutôt, -k).

   Et donc enfin, (S) et (F) se retrouveront à la position (0 - k), soit (k) nœuds du début de la boucle.

4. Compte tenu de [3] ci-dessus, comme (k) représente l'avance (k) que (F) avait, et comme (F) a parcouru 2X la distance parcourue par (S) pour entrer dans la boucle depuis la tête de la liste, (k) représente également la distance depuis le début de la liste, ce qui représente donc le début de la boucle.

Il est un peu tard ici alors j'espère avoir bien articulé. Faites-le moi savoir sinon et je vais essayer de mettre à jour ma réponse.

Answer 4

Si l'utilisation d'une carte de hachage d'identité (comme IdentityHashMap) est autorisée, cela est très facile à résoudre. Cela utilise cependant plus d'espace.

Parcourir la liste des nœuds. Pour chaque nœud rencontré, l'ajouter à 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 précédent ce conflit est connu (vérifiez avant de bouger ou gardez le "dernier nœud") -- définissez simplement "next" de manière appropriée pour casser le cycle.

Suivre cette approche simple devrait être un exercice amusant : le code est laissé à la discrétion du lecteur.

Joyeux codage.

Answer 5

 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

Insérer un nœud fictif après chaque nœud de la liste chaînée et avant son insertion, vérifier que le nœud suivant est fictif ou non. Si le nœud suivant est fictif, insérer null dans le prochain de ce nœud.