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

//Trouver une boucle dans une liste chaînée et supprimer le lien entre les nœuds

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 Boucle trouvée");
                isLoopExist = true;
                break;
            }
        }
        if (isLoopExist) {
            slowNode = head;
            Node prevNode = null;
            while (slowNode != fastNode) {
                prevNode = fastNode;
                fastNode = fastNode.next;
                slowNode = slowNode.next;
            }
            System.out.print("Nœud de la boucle trouvé : " + slowNode.mData);
            prevNode.next = null; //Supprimer la boucle
        }
    }

:)GlbMP

Answer 2

La façon la plus facile et unique

Pour résoudre ce problème, il suffit de compter le nombre de nœuds (c'est tout). Je parie que vous n'avez pas encore vu cette solution sur un site web de compétition, car je l'ai créée aujourd'hui par moi-même...

void removeTheLoop(Node *root)
{
    std :: unordered_set < struct Node * > s;
    if(root == NULL)
        return ;

    s.insert(root);
    int before_size = s.size();

    while(1)
    {
        if(root -> next == NULL)
            return;
        s.insert(root -> next);
        if(before_size == s.size())
        {
            root -> next = NULL;
            return;
        }
        before_size = s.size();
        root = root -> next;
    }
}

Comment ça marche:

COMPLEXITÉ TEMPORELLE: O(n)...COMPLEXITÉ ESPACE: O(n)

• Il compte simplement le nombre d'éléments. Nous utiliserons unordered_set en c++.
• Il insère l'élément s'il n'est pas présent dans le conteneur et augmente sa taille.
• Maintenant le suspense commence lorsque le nœud pointe vers un nœud déjà ajouté, dans ce cas, la taille ne augmente pas et nous rendrons son suivant NULL.

UPVOTEZ SI VOUS PENSEZ QUE C'EST UNIQUE.