Wie erkennt man eine Schleife in einer verknüpften Liste?

Question

Angenommen, Sie haben eine verknüpfte Listenstruktur in Java. Sie besteht aus Nodes:

class Node {
    Node next;
    // some user data
}

und jeder Knoten verweist auf den nächsten Knoten, mit Ausnahme des letzten Knotens, bei dem der nächste Knoten Null ist. Angenommen, es besteht die Möglichkeit, dass die Liste eine Schleife enthält - d. h. der letzte Knoten hat statt einer Null einen Verweis auf einen der Knoten in der Liste, der vor ihm lag.

Was ist die beste Art zu schreiben?

boolean hasLoop(Node first)

die Folgendes zurückgeben würde true wenn der angegebene Knoten der erste einer Liste mit einer Schleife ist, und false sonst? Wie könnte man so schreiben, dass der Platzbedarf gleich bleibt und die Zeit angemessen ist?

Das folgende Bild zeigt, wie eine Liste mit einer Schleife aussieht:

Answer 1

Sie können Folgendes nutzen Floyd's Zyklusfindungsalgorithmus , auch bekannt als Algorithmus für Schildkröte und Hase .

Die Idee ist, zwei Verweise auf die Liste zu haben und sie bei unterschiedliche Geschwindigkeiten . Einen Schritt nach vorne machen durch 1 Knoten und den anderen durch 2 Knotenpunkte.

• Wenn die verknüpfte Liste eine Schleife hat, dann wird definitiv treffen.
• Andernfalls wird entweder der beiden Referenzen (oder deren next ) wird zu null .

Java-Funktion zur Implementierung des Algorithmus:

boolean hasLoop(Node first) {

    if(first == null) // list does not exist..so no loop either
        return false;

    Node slow, fast; // create two references.

    slow = fast = first; // make both refer to the start of the list

    while(true) {

        slow = slow.next;          // 1 hop

        if(fast.next != null)
            fast = fast.next.next; // 2 hops
        else
            return false;          // next node null => no loop

        if(slow == null || fast == null) // if either hits null..no loop
            return false;

        if(slow == fast) // if the two ever meet...we must have a loop
            return true;
    }
}

Answer 2

Hier ist eine Verfeinerung der Fast/Slow-Lösung, die Listen mit ungerader Länge korrekt behandelt und die Übersichtlichkeit verbessert.

boolean hasLoop(Node first) {
    Node slow = first;
    Node fast = first;

    while(fast != null && fast.next != null) {
        slow = slow.next;          // 1 hop
        fast = fast.next.next;     // 2 hops 

        if(slow == fast)  // fast caught up to slow, so there is a loop
            return true;
    }
    return false;  // fast reached null, so the list terminates
}

Answer 3

Besser als Floyds Algorithmus

Richard Brent beschrieb eine alternativer Zykluserkennungsalgorithmus was ziemlich genau dem Hasen und der Schildkröte [Floyds Zyklus] entspricht, mit dem Unterschied, dass sich der langsame Knoten hier nicht bewegt, sondern später in festen Abständen an die Position des schnellen Knotens "teleportiert" wird.

Die Beschreibung ist verfügbar unter Brent's Cycle Detection Algorithmus (Die teleportierende Schildkröte) . Brent behauptet, dass sein Algorithmus 24 bis 36 % schneller ist als der Zyklusalgorithmus von Floyd. O(n) Zeitkomplexität, O(1) Raumkomplexität.

public static boolean hasLoop(Node root) {
    if (root == null) return false;

    Node slow = root, fast = root;
    int taken = 0, limit = 2;

    while (fast.next != null) {
        fast = fast.next;
        taken++;
        if (slow == fast) return true;

        if (taken == limit) {
            taken = 0;
            limit <<= 1;    // equivalent to limit *= 2;
            slow = fast;    // teleporting the turtle (to the hare's position) 
        }
    }
    return false;
}

Answer 4

Eine alternative Lösung zu Schildkröte und Kaninchen, nicht ganz so schön, da ich die Liste vorübergehend ändere:

Die Idee ist, die Liste abzuarbeiten und sie dabei umzukehren. Wenn Sie dann zum ersten Mal einen Knoten erreichen, der bereits besucht wurde, zeigt der nächste Zeiger "rückwärts", so dass die Iteration in Richtung first wieder, wo sie endet.

Node prev = null;
Node cur = first;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
boolean hasCycle = prev == first && first != null && first.next != null;

// reconstruct the list
cur = prev;
prev = null;
while (cur != null) {
    Node next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}

return hasCycle;

Test-Code:

static void assertSameOrder(Node[] nodes) {
    for (int i = 0; i < nodes.length - 1; i++) {
        assert nodes[i].next == nodes[i + 1];
    }
}

public static void main(String[] args) {
    Node[] nodes = new Node[100];
    for (int i = 0; i < nodes.length; i++) {
        nodes[i] = new Node();
    }
    for (int i = 0; i < nodes.length - 1; i++) {
        nodes[i].next = nodes[i + 1];
    }
    Node first = nodes[0];
    Node max = nodes[nodes.length - 1];

    max.next = null;
    assert !hasCycle(first);
    assertSameOrder(nodes);
    max.next = first;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = max;
    assert hasCycle(first);
    assertSameOrder(nodes);
    max.next = nodes[50];
    assert hasCycle(first);
    assertSameOrder(nodes);
}

Answer 5

Schildkröte und Hase

Werfen Sie einen Blick auf Pollard's rho-Algorithmus . Es ist nicht ganz dasselbe Problem, aber vielleicht verstehen Sie die Logik und können sie auf verknüpfte Listen anwenden.

(wenn Sie zu faul sind, können Sie einfach nachsehen Zykluserkennung -- (siehe den Teil über die Schildkröte und den Hasen).

Dies erfordert nur lineare Zeit und 2 zusätzliche Zeiger.

In Java:

boolean hasLoop( Node first ) {
    if ( first == null ) return false;

    Node turtle = first;
    Node hare = first;

    while ( hare.next != null && hare.next.next != null ) {
         turtle = turtle.next;
         hare = hare.next.next;

         if ( turtle == hare ) return true;
    }

    return false;
}

(Die meisten Lösungen prüfen nicht auf beide next y next.next für Nullen. Da die Schildkröte immer hinten liegt, muss man sie auch nicht auf Nullen prüfen - das hat der Hase schon getan).