webentwicklung-frage-antwort-db.com.de

Interview: Remove Loop in verknüpfter Liste - Java

Ich wurde im Interview mit dieser Frage gefragt: "Wie kann ich die Schleife in der verknüpften Liste erkennen?" Ich fummelte.

Also, irgendwelche Hinweise, wie man dieses Problem lösen kann, können Pseudo-Code oder Methodendefinition sein?

Ich bin mit Java vertraut, daher habe ich diese Frage unter Java markiert.

Für die Instanz hat diese verknüpfte Liste eine Schleife

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

Dieses Problem besteht aus zwei Teilen:

  1. Ermitteln Sie, ob die Liste eine Schleife enthält
  2. Identifizieren Sie den Anfang der Schleife

Sobald Sie wissen, wo die Schleife beginnt, können Sie das letzte Element in der Liste leicht identifizieren, da es sich um das Element in der Liste handelt, das auf den Anfang der Schleife folgt und dann wieder auf den Anfang der Schleife zeigt. Es ist dann trivial, den nächsten Zeiger/die nächste Referenz dieses Elements auf null zu setzen, um die Liste der zyklischen Verknüpfungen zu korrigieren (nicht die Liste der zirkulären Verknüpfungen, bei der das letzte Element auf das erste verweist - dies wäre eine bestimmte Instanz von zyklische Listen).

  1. Floyds Zykluserkennungsalgorithmus, auch Schildkröten- und Hasenalgorithmus genannt Die Verwendung von zwei Zeigern/Referenzen, die sich mit unterschiedlicher Geschwindigkeit bewegen, ist eine Möglichkeit, den Zyklus zu erkennen. Wenn es einen Zyklus gibt, zeigen die beiden Zeiger (sagen Sie p1 und p2) nach einer endlichen Anzahl von Schritten auf dasselbe Element. Interessanterweise kann bewiesen werden, dass das Element, an dem sie sich treffen, den gleichen Abstand zum Anfang der Schleife hat ( Fahren Sie mit dem Durchlaufen der Liste in derselben Vorwärtsrichtung fort), während sich der Beginn der Schleife am Anfang der Liste befindet. Das heißt, wenn der lineare Teil der Liste k Elemente enthält, treffen sich die beiden Zeiger innerhalb der Schleife der Länge m an einem Punkt m-k vom Anfang der Schleife oder k Elemente zum 'Ende' der Schleife (natürlich ist es eine Schleife, so dass es kein 'Ende' gibt - es ist nur noch einmal der 'Anfang'). Und so finden wir den Anfang der Schleife:

  2. Nachdem ein Zyklus erkannt wurde, zeige p2 weiterhin auf das Element, in dem die Schleife für den obigen Schritt beendet wurde, setze p1 jedoch zurück, so dass sie auf den Kopf der Liste zeigt. Bewegen Sie nun jeden Zeiger um jeweils ein Element. Da p2 innerhalb der Schleife begonnen hat, wird die Schleife fortgesetzt. Nach k Schritten (gleich dem Abstand des Schleifenanfangs vom Kopf der Liste) treffen sich p1 und p2 erneut. Dies gibt Ihnen einen Verweis auf den Beginn der Schleife.

  3. Es ist jetzt einfach, p1 (oder p2) so einzustellen, dass es auf das Element zeigt, das die Schleife startet, und die Schleife zu durchlaufen, bis p1 auf das Startelement zeigt. Zu diesem Zeitpunkt verweist p1 auf die 'letzte' Elementliste, und sein nächster Zeiger kann auf null gesetzt werden.


Hier ist ein schneller und unsauberer Java Code, der eine verknüpfte Liste von Nodes voraussetzt, wobei Node eine next Referenz hat. Dies könnte optimiert werden, aber es sollte Ihnen die Grundidee geben:

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

Diese Erklärung könnte das Warum hinter Teil II helfen:

Angenommen, die Länge des Zyklus ist M und die Länge des Restes der verknüpften Liste ist L. Lassen Sie uns herausfinden, an welcher Stelle im Zyklus t1/t2 zum ersten Mal aufeinander treffen?

Definieren Sie, dass der erste Knoten im Zyklus die Position 0 ist und folgen Sie den Links, die wir an den Positionen 1, 2, ... bis M-1 haben. (Wenn wir im Zyklus gehen, ist unsere aktuelle Position (walk_length) mod M, richtig?) Angenommen, t1/t2 treffen sich zuerst an Position p, dann ist ihre Fahrzeit dieselbe (L + k1 * M + p)/v = (L + k2 · M + p)/2v für etwas k1

Daraus folgt, dass wenn t1 von p startet, t2 von Kopf startet und sich mit der gleichen Geschwindigkeit bewegt, der erste Knoten des Zyklus an Position 0 erreicht wird. QED.

Weitere Referenzen:

61

Lösung 1 - mit freundlicher Genehmigung von Career Cup und "Cracking the Coding Interview" Buch :

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

Die Erklärung für diese Lösung stammt direkt aus dem Buch:

Wenn wir zwei Zeiger verschieben, einen mit Geschwindigkeit 1 und eine andere mit Geschwindigkeit 2, sie wird am Ende treffen, wenn die verknüpften Liste hat eine Schleife. Warum? Denken Sie an zwei Autos fahren auf einer Spur; das schnellere Auto wird immer das langsamere passieren! 

Der schwierige Teil hier ist das Finden des Starts der Schleife. Stellen Sie sich als Analogie vor, zwei Leute, die um eine Spur rennen, einer läuft doppelt so schnell wie der andere. Beginnen sie gleichzeitig Wann werden sie sich als nächstes treffen? Sie wird sich als nächstes beim Start der nächste Runde.

Nehmen wir an, Fast Runner hatte einen Vorsprung von k Metern auf eine n-Schritt-Runde. Wann werden sie als nächstes Treffen? Sie werden k Meter vor __ treffen. der Beginn der nächsten Runde. (Warum? Schnell Läufer hätte k + 2 (n - k) Schritte gemacht, einschließlich des Kopfanfangs und Langsame Läufer hätte n - k Schritte gemacht. Beide werden k Schritte sein vor dem Start der Schleife).

Nun geht es zurück zum Problem, wenn Fast Runner (n2) und Langsamer Läufer (n1) bewegen sich um unseren zirkuläre verknüpfte Liste, n2 hat eine Kopfstart in der Schleife, wenn n1 tritt ein Insbesondere hat es eine Kopfanfang von k, wobei k die Zahl ist von Knoten vor der Schleife. Da hat n2 ein Kopfanfang von k Knoten, n1 und n2 trifft k Knoten vor dem Start von die Schleife.

So wissen wir jetzt folgendes: 

  1. Kopf ist k Knoten von LoopStart (per Definition) 
  2. MeetingPoint für n1 und n2 ist k Knoten von LoopStart (wie oben gezeigt)

Wenn wir also n1 zurück zu Head verschieben und n2 bei MeetingPoint behalten und beide im gleichen Tempo bewegen, werden sie sich bei LoopStart treffen

Lösung 2 - mit freundlicher Genehmigung von mir :)

public static LinkedListNode findHeadOfLoop(LinkedListNode head) {

    int indexer = 0;
    Map<LinkedListNode, Integer> map = new IdentityHashMap<LinkedListNode, Integer>();
    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;
}

Ich hoffe das hilft.
Hristo

14
Hristo

Diese Antwort ist nicht dazu gedacht, sich um die Antwort zu bewerben, sondern um etwas mehr über das Zusammentreffen der beiden Knoten in der Schildkröte und dem Hasenalgorithmus zu erklären.

  1. Beide Knoten treten schließlich in die Schleife ein. Da sich einer schneller (F) als der andere (S) bewegt, wird (F) eventuell überlaufen (S).

  2. Wenn der Start der Schleife am Kopf der Liste ist, muss (F) sich am Kopf der Liste treffen (S). Dies ist NUR, weil die Geschwindigkeit von (F) 2X (S) ist; Wenn es 3X wäre, wäre das nicht wahr. Dies ist der Fall, da (F) eine Runde abschließt, wenn (S) eine halbe Runde abschließt. Wenn (S) seine erste Runde abschließt, hat (F) zwei Runden zurückgelegt - und ist mit (S) wieder am Anfang der Schleife. .

  3. Wenn der Start der Schleife NICHT am Kopf der Liste ist, dann hat (F) zu der Zeit, zu der (S) in die Schleife eintritt, einen Kopfanfang von (k) Knoten in der Schleife. Da die Geschwindigkeit von (S) jeweils nur ein Knoten ist, trifft sie (F) an (k) Knoten vom Start der Schleife an - wie in, (k) weitere Schritte vor dem Start, NICHT (k) Schritte NACH der Beginn. Dies wäre NICHT wahr, wenn die Geschwindigkeit von (S) nicht eins war und das Geschwindigkeitsverhältnis zwischen (F) und (S) nicht 2: 1 war.

    3.1. Hier wird es ein bisschen schwierig zu erklären. Wir können uns darauf einigen, dass (F) weiterhin überlappt (S), bis sie sich schließlich treffen (siehe 1 oben), aber warum bei (k) Knoten vom Anfang der Schleife an? Man betrachte die folgende Gleichung, wobei M die Anzahl der Knoten oder die Entfernung der Schleife ist und k der Kopfanfang (F) war; die Gleichung repräsentiert die zurückgelegte Strecke (F) der angegebenen Zeit t links in Bezug auf die zurückgelegte Strecke (S) rechts:

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

    Wenn also (S) in die Schleife eintritt und die Strecke um 0 zurückgelegt wurde, hat (F) nur die Entfernung (k) zurückgelegt. Zu der Zeit d_S = M - k ist d_F = 2M - k. Da wir auch die modulare Mathematik verwenden müssen, da M die Gesamtdistanz einer einzelnen Runde in der Schleife darstellt, ist die POSITION von (F) und (S) an einem ganzen M (kein Rest) 0. Also dann in Bezug auf POSITION (oder das Differential), lässt k (bzw. -k) zurück.

    Und schließlich treffen sich (S) und (F) an Positionen (0 - k) oder (k) Knoten vom Start der Schleife entfernt.

  4. [3] gegeben, da (k) den Kopfanfang (F) repräsentiert hat und (F) 2X die zurückgelegte Entfernung (S) zurückgelegt hat, um die Schleife vom Kopf der Liste zu betreten, (k) auch die Abstand vom Start der Liste, der dann den Start der Schleife darstellt.

Es ist etwas spät hier, also hoffe ich, dass ich mich effektiv artikulieren kann. Lass es mich anders wissen und ich werde versuchen, meine Antwort zu aktualisieren.

6
bitxwise

Wenn die Verwendung einer Identity-Hash-Map (wie IdentityHashMap ) zulässig ist, ist dies äußerst einfach zu lösen. Es benötigt jedoch mehr Platz.

Durchsuchen Sie die Knotenliste. Fügen Sie ihn für jeden Knoten der Identitätskarte hinzu. Wenn der Knoten bereits in der Identitätskarte vorhanden war, hat die Liste eine zirkuläre Verbindung, und der vor diesem Konflikt bestehende Knoten ist bekannt (entweder vor dem Verschieben prüfen oder den "letzten Knoten" behalten) - einfach "next" entsprechend setzen den Kreislauf durchbrechen.

Dieser einfache Ansatz sollte eine unterhaltsame Übung sein: Code bleibt dem Leser als Übung überlassen.

Glückliche Kodierung.

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

Fügen Sie einen Dummy-Knoten nach jedem Knoten der Linkliste ein und prüfen Sie vor dem Einfügen, ob der nächste Knoten Dummy ist oder nicht. Wenn next für next ein Dummy ist, fügen Sie in diesem Knoten den Wert null ein. 

 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
3
Parag Bafna
//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

0