Interview: Schleife in verknüpfter Liste entfernen - Java

Question

Diese Frage wurde mir im Vorstellungsgespräch gestellt: "Wie erkennt man eine Schleife in einer verknüpften Liste?", ich löste diese Frage, aber sofort fragte mich der Interviewer, wie ich die Schleife in einer verknüpften Liste entfernen kann. Ich fummelte.

So alle Hinweise auf, wie dies zu lösen, kann Pseudo-Code oder Methode Definition sein?

Ich kenne mich mit Java gut aus, daher habe ich diese Frage unter Java getaggt.

Diese verknüpfte Liste hat zum Beispiel eine Schleife

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

Answer 1

//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; //Remove the Loop
            }
        }

:)GlbMP

Answer 2

Einfachster und einzigartiger Weg

Um dieses Problem zu lösen, zählen wir einfach die Anzahl der Knoten ( das war's ). Ich wette, Sie haben diese Lösung bis jetzt noch auf keiner Konkurrenz-Website gesehen, denn ich habe sie heute selbst gemacht...

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

Wie es funktioniert:

ZEITKOMPLEXITÄT: O(n)...RAUMKOMPLEXITÄT: O(n)

• Sie zählt einfach die Anzahl der Elemente. Wir werden unordered_set in C++ verwenden.
• Es fügt das Element ein, wenn es nicht im Container vorhanden ist, und vergrößert es.
• Jetzt fängt die Spannung an, wenn der Knoten kommt, der auf den Knoten zeigt, der bereits hinzugefügt wurde, so dass in diesem Fall die Größe nicht zunimmt und wir als nächstes NULL machen werden.

BEWERTEN SIE IHN HOCH, WENN SIE IHN FÜR EINZIGARTIG HALTEN.