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

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.

Answer 2

Man könnte es sogar in konstanter O(1)-Zeit machen (obwohl es nicht sehr schnell oder effizient wäre): Es gibt eine begrenzte Anzahl von Knoten, die der Speicher Ihres Computers aufnehmen kann, sagen wir N Datensätze. Wenn Sie mehr als N Datensätze durchlaufen, dann haben Sie eine Schleife.

Answer 3

Die Erkennung einer Schleife in einer verknüpften Liste kann auf eine der einfachsten Arten erfolgen, was zu einer Komplexität von O(N) bei der Verwendung von Hashmaps oder O(NlogN) bei einem sortierbasierten Ansatz führt.

Erstellen Sie eine sortierte Liste der Adressen, indem Sie die Liste vom Kopf aus durchgehen. Wenn Sie eine neue Adresse einfügen, prüfen Sie, ob die Adresse bereits in der sortierten Liste enthalten ist, was O(logN) Komplexität erfordert.

Answer 4

Hier ist mein lauffähiger Code.

Ich habe die verknüpfte Liste mit Hilfe von drei temporären Knoten wiederhergestellt (Raumkomplexität O(1) ), die den Überblick über die Links behalten.

Das Interessante daran ist, dass es hilft, den Zyklus in der verknüpften Liste zu erkennen, denn wenn man vorwärts geht, erwartet man nicht, dass man zum Ausgangspunkt (Wurzelknoten) zurückkehrt, und einer der temporären Knoten sollte auf Null gehen, es sei denn, man hat einen Zyklus, was bedeutet, dass er auf den Wurzelknoten zeigt.

Die Zeitkomplexität dieses Algorithmus ist O(n) und die Raumkomplexität ist O(1) .

Hier ist der Klassenknoten für die verknüpfte Liste:

public class LinkedNode{
    public LinkedNode next;
}

Hier ist der Hauptcode mit einem einfachen Testfall mit drei Knoten, wobei der letzte Knoten auf den zweiten Knoten verweist:

    public static boolean checkLoopInLinkedList(LinkedNode root){

        if (root == null || root.next == null) return false;

        LinkedNode current1 = root, current2 = root.next, current3 = root.next.next;
        root.next = null;
        current2.next = current1;

        while(current3 != null){
            if(current3 == root) return true;

            current1 = current2;
            current2 = current3;
            current3 = current3.next;

            current2.next = current1;
        }
        return false;
    }

Hier ist ein einfacher Testfall mit drei Knoten, wobei der letzte Knoten auf den zweiten Knoten verweist:

public class questions{
    public static void main(String [] args){

        LinkedNode n1 = new LinkedNode();
        LinkedNode n2 = new LinkedNode();
        LinkedNode n3 = new LinkedNode();
        n1.next = n2;
        n2.next = n3;
        n3.next = n2;

        System.out.print(checkLoopInLinkedList(n1));
    }
}

Answer 5

 // To detect whether a circular loop exists in a linked list
public boolean findCircularLoop() {
    Node slower, faster;
    slower = head;
    faster = head.next; // start faster one node ahead
    while (true) {

        // if the faster pointer encounters a NULL element
        if (faster == null || faster.next == null)
            return false;
        // if faster pointer ever equals slower or faster's next
        // pointer is ever equal to slower then it's a circular list
        else if (slower == faster || slower == faster.next)
            return true;
        else {
            // advance the pointers
            slower = slower.next;
            faster = faster.next.next;
        }
    }
}