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

In diesem Zusammenhang gibt es überall viel Textmaterial. Ich wollte nur eine schematische Darstellung veröffentlichen, die mir wirklich geholfen hat, das Konzept zu begreifen.

Wenn sich schnell und langsam im Punkt p treffen,

Schnell zurückgelegte Strecke = a+b+c+b = a+2b+c

Langsam zurückgelegte Strecke = a+b

Denn der Schnelle ist 2-mal schneller als der Langsame. Also a+2b+c = 2(a+b) , dann erhalten wir a=c .

Wenn also ein anderer langsamer Zeiger wieder von Kopf bis q , gleichzeitig läuft der schnelle Zeiger von p bis q so dass sie sich an dem Punkt treffen q zusammen.

public ListNode detectCycle(ListNode head) {
    if(head == null || head.next==null)
        return null;

    ListNode slow = head;
    ListNode fast = head;

    while (fast!=null && fast.next!=null){
        fast = fast.next.next;
        slow = slow.next;

        /*
        if the 2 pointers meet, then the 
        dist from the meeting pt to start of loop 
        equals
        dist from head to start of loop
        */
        if (fast == slow){ //loop found
            slow = head;
            while(slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }            
    }
    return null;
}

Answer 2

Der Benutzer unicornaddict hat einen schönen Algorithmus, aber leider enthält er einen Fehler für nicht-loopy Listen mit ungerader Länge >= 3. Das Problem ist, dass fast kann kurz vor dem Ende der Liste "stecken bleiben", slow auf, und eine Schleife wird (fälschlicherweise) erkannt.

Hier ist der korrigierte Algorithmus.

static 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 = null;
        else
            fast = fast.next.next; // 2 hops.

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

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

Answer 3

Algorithmus

public static boolean hasCycle (LinkedList<Node> list)
{
    HashSet<Node> visited = new HashSet<Node>();

    for (Node n : list)
    {
        visited.add(n);

        if (visited.contains(n.next))
        {
            return true;
        }
    }

    return false;
}

Komplexität

Time ~ O(n)
Space ~ O(n)

Answer 4

Die folgende Methode ist vielleicht nicht die beste - sie ist O(n^2). Sie sollte jedoch dazu dienen, die Aufgabe (irgendwann) zu erledigen.

count_of_elements_so_far = 0;
for (each element in linked list)
{
    search for current element in first <count_of_elements_so_far>
    if found, then you have a loop
    else,count_of_elements_so_far++;
}

Answer 5

public boolean hasLoop(Node start){   
   TreeSet<Node> set = new TreeSet<Node>();
   Node lookingAt = start;

   while (lookingAt.peek() != null){
       lookingAt = lookingAt.next;

       if (set.contains(lookingAt){
           return false;
        } else {
        set.put(lookingAt);
        }

        return true;
}   
// Inside our Node class:        
public Node peek(){
   return this.next;
}

Verzeihen Sie mir meine Unwissenheit (ich bin noch ziemlich neu in Java und Programmierung), aber warum sollte das oben genannte nicht funktionieren?

Ich schätze, das löst nicht das Problem des konstanten Platzes... aber es erreicht das Ziel zumindest in einer angemessenen Zeit, richtig? Es wird nur den Platz der verknüpften Liste plus den Platz einer Menge mit n Elementen benötigen (wobei n die Anzahl der Elemente in der verknüpften Liste oder die Anzahl der Elemente bis zum Erreichen einer Schleife ist). Und was die Zeit angeht, so würde eine Worst-Case-Analyse, denke ich, O(nlog(n)) vorschlagen. SortedSet Look-ups für contains() sind log(n) (überprüfen Sie die javadoc, aber ich bin ziemlich sicher, TreeSet zugrunde liegende Struktur ist TreeMap, deren wiederum ist ein rot-schwarz-Baum), und im schlimmsten Fall (keine Schleifen, oder Schleife ganz am Ende), wird es n Look-ups zu tun haben.