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

Hier ist die Lösung, um den Zyklus zu erkennen.

public boolean hasCycle(ListNode head) {
            ListNode slow =head;
            ListNode fast =head;

            while(fast!=null && fast.next!=null){
                slow = slow.next; // slow pointer only one hop
                fast = fast.next.next; // fast pointer two hops 

                if(slow == fast)    return true; // retrun true if fast meet slow pointer
            }

            return false; // return false if fast pointer stop at end 
        }

Answer 2

Sie können auch den Schildkrötenalgorithmus von Floyd verwenden, wie in den obigen Antworten vorgeschlagen.

Dieser Algorithmus kann prüfen, ob eine einfach verkettete Liste einen geschlossenen Zyklus hat. Dies kann erreicht werden, indem eine Liste mit zwei Zeigern iteriert wird, die sich mit unterschiedlicher Geschwindigkeit bewegen. Wenn es einen Zyklus gibt, treffen sich die beiden Zeiger an einem bestimmten Punkt in der Zukunft.

Bitte schauen Sie sich auch meine Blog-Beitrag über die Datenstruktur der verknüpften Listen, in der ich auch einen Codeschnipsel mit einer Implementierung des oben erwähnten Algorithmus in der Sprache Java enthalten habe.

Herzliche Grüße,

Andreas (@xnorcode)

Answer 3

Hier ist meine Lösung in Java

boolean detectLoop(Node head){
    Node fastRunner = head;
    Node slowRunner = head;
    while(fastRunner != null && slowRunner !=null && fastRunner.next != null){
        fastRunner = fastRunner.next.next;
        slowRunner = slowRunner.next;
        if(fastRunner == slowRunner){
            return true;
        }
    }
    return false;
}

Answer 4

Dieser Code ist optimiert und wird das Ergebnis schneller als mit der einen als die beste Antwort gewählt zu produzieren.dieser Code spart in einen sehr langen Prozess der Verfolgung der vorwärts und rückwärts Knotenzeiger, die im folgenden Fall auftreten, wenn wir die "beste Antwort" Methode folgen.schauen Sie durch den Trockenlauf der folgenden und Sie werden erkennen, was ich versuche zu sagen.dann schauen Sie sich das Problem durch die angegebene Methode unten und messen die Anzahl der Schritte, um die Antwort zu finden.

1->2->9->3 ^--------^

Hier ist der Code:

boolean loop(node *head)
{
 node *back=head;
 node *front=head;

 while(front && front->next)
 {
  front=front->next->next;
  if(back==front)
  return true;
  else
  back=back->next;
 }
return false
}

Answer 5

Dieser Ansatz hat einen Platzbedarf, aber eine einfachere Implementierung:

Schleifen können durch Speicherung von Knoten in einer Map identifiziert werden. Vor dem Einfügen des Knotens muss geprüft werden, ob der Knoten bereits existiert. Wenn der Knoten bereits in der Map existiert, bedeutet das, dass die Linked List eine Schleife hat.

public boolean loopDetector(Node<E> first) {  
       Node<E> t = first;  
       Map<Node<E>, Node<E>> map = new IdentityHashMap<Node<E>, Node<E>>();  
       while (t != null) {  
            if (map.containsKey(t)) {  
                 System.out.println(" duplicate Node is --" + t  
                           + " having value :" + t.data);  

                 return true;  
            } else {  
                 map.put(t, t);  
            }  
            t = t.next;  
       }  
       return false;  
  }