Wie erkenne ich eine Schleife in einer verknüpften Liste?

434

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

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

und jeder Knoten zeigt auf den nächsten Knoten, mit Ausnahme des letzten Knotens, der für den nächsten Null hat. Angenommen, es besteht die Möglichkeit, dass die Liste eine Schleife enthält - dh der letzte Knoten hat anstelle einer Null einen Verweis auf einen der Knoten in der Liste, die davor standen.

Was ist die beste Art zu schreiben?

boolean hasLoop(Node first)

Was würde zurückkehren, truewenn der angegebene Knoten der erste einer Liste mit einer Schleife ist, und falseansonsten? Wie können Sie so schreiben, dass es konstant viel Platz und eine angemessene Zeit benötigt?

Hier ist ein Bild davon, wie eine Liste mit einer Schleife aussieht:

Alt-Text

jjujuma
quelle
50
Wow..Ich würde gerne für diesen Arbeitgeber arbeiten finite amount of space and a reasonable amount of time?:)
Codaddict
10
@SLaks - Die Schleife muss nicht zum ersten Knoten zurückgeschleift werden. Es kann bis zur Hälfte zurücklaufen.
Jjujuma
109
Die folgenden Antworten sind lesenswert, aber Interviewfragen wie diese sind schrecklich. Sie kennen entweder die Antwort (dh Sie haben eine Variante von Floyds Algorithmus gesehen) oder Sie wissen es nicht und es tut nichts, um Ihre Argumentation oder Ihre Entwurfsfähigkeit zu testen.
GaryF
3
Um fair zu sein, die meisten "wissenden Algorithmen" sind so - es sei denn, Sie machen Dinge auf Forschungsebene!
Larry
12
@ GaryF Und doch wäre es aufschlussreich zu wissen, was sie tun würden, wenn sie die Antwort nicht wüssten. ZB welche Schritte würden sie unternehmen, mit wem würden sie zusammenarbeiten, was würden sie tun, um einen Mangel an algorithmischem Wissen zu überwinden?
Chris Knight

Antworten:

538

Sie können den Zyklusfindungsalgorithmus von Floyd verwenden , der auch als Schildkröten- und Hasenalgorithmus bezeichnet wird .

Die Idee ist, zwei Verweise auf die Liste zu haben und sie mit unterschiedlicher Geschwindigkeit zu verschieben . Bewegen Sie einen nach 1Knoten vorwärts und den anderen nach 2Knoten.

  • Wenn die verknüpfte Liste eine Schleife hat, werden sie sich definitiv treffen.
  • Andernfalls wird eine der beiden Referenzen (oder deren next) 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;
    }
}
Codaddict
quelle
29
Sie müssen auch eine fast.nextnextif(fast.next!=null)fast=fast.next.next;
Nullprüfung durchführen,
12
Sie sollten nicht nur überprüfen (langsam == schnell), sondern auch: (langsam == schnell || langsam.next == schnell), um zu verhindern, dass das schnelle über das langsame
springt
13
Ich habe
mich
4
Die Prüfung auf slow == null ist redundant, es sei denn, die Liste enthält nur einen Knoten. Sie können auch einen Aufruf von Node.next entfernen. Hier ist eine einfachere und schnellere Version der Schleife: pastie.org/927591
Kay Sarraute
22
Sie sollten wirklich Ihre Referenzen zitieren. Dieser Algorithmus wurde in den 60er Jahren von Robert Floyd erfunden. Er ist als Floyds Algorithmus zur Zyklusfindung bekannt, auch bekannt als. Der Schildkröten- und Hasenalgorithmus.
Joshperry
127

Hier ist eine Verfeinerung der Fast / Slow-Lösung, die Listen mit ungeraden Längen korrekt verarbeitet und die Klarheit 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
}
Dave L.
quelle
2
Schön und prägnant. Dieser Code kann optimiert werden, indem überprüft wird, ob langsam == schnell || (fast.next! = null && slow = fast.next); :)
arachnode.net
11
@ arachnode.net Das ist keine Optimierung. Wenn slow == fast.nextdann slowwird gleich fastbei der nächsten Iteration; Es wird höchstens eine Iteration auf Kosten eines zusätzlichen Tests für jede Iteration gespeichert.
Jason C
@ ana01 slowkann vorher nicht null werden, fastda es dem gleichen Referenzpfad folgt (es sei denn, Sie haben die Liste gleichzeitig geändert. In diesem Fall sind alle Wetten deaktiviert).
Dave L.
Wie funktioniert das aus Neugier für ungerade Zahlen? Kannst du die Schildkröte nicht immer noch auf verknüpften Listen mit ungerader Länge weitergeben?
TheGreenCabbage
1
@theGreenCabbage Mit jeder Iteration der Schleife kommt der Hase der Schildkröte einen Schritt weiter. Wenn der Hase also 3 Schritte zurückliegt, dauert die nächste Iteration zwei Sprünge und die Schildkröte einen Sprung, und jetzt ist der Hase 2 Schritte zurück. Nach der nächsten Iteration liegt der Hase 1 Sprung zurück und wird dann genau eingeholt. Wenn der Hase 3 Sprünge gemacht hat, während die Schildkröte einen gemacht hat, kann er überspringen, weil er jedes Mal um 2 zunimmt, aber da er bei jeder Iteration nur um 1 zunimmt, kann er nicht überspringen.
Dave L.
52

Besser als Floyds Algorithmus

Richard Brent beschrieb einen alternativen Zykluserkennungsalgorithmus , der dem Hasen und der Schildkröte [Floyds Zyklus] ziemlich ähnlich ist, außer dass sich der langsame Knoten hier nicht bewegt, sondern später an die Position des schnellen Knotens bei fest "teleportiert" wird Intervalle.

Die Beschreibung finden Sie hier: http://www.siafoo.net/algorithm/11 Brent behauptet, sein Algorithmus sei 24 bis 36% schneller als der Floyd-Zyklusalgorithmus. 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;
}
Ashok Bijoy Debnath
quelle
Diese Antwort ist fantastisch!
Valin077
1
Ihre Antwort hat mir sehr gut gefallen und sie in meinen Blog aufgenommen - k2code.blogspot.in/2010/04/… .
Kinshuk4
Warum müssen Sie überprüfen slow.next != null? Soweit ich sehen kann slowist immer hinter oder gleich fast.
TWiStErRob
Das habe ich vor langer Zeit gemacht, als ich anfing, Algorithmen zu lernen. Code bearbeitet. Danke :)
Ashok Bijoy Debnath
50

Eine alternative Lösung zu Turtle and Rabbit, nicht ganz so schön, da ich die Liste vorübergehend ändere:

Die Idee ist, die Liste zu durchlaufen und sie im Laufe der Zeit umzukehren. Wenn Sie dann zum ersten Mal einen Knoten erreichen, der bereits besucht wurde, zeigt sein nächster Zeiger "rückwärts", wodurch die Iteration wieder in Richtung firstfortgesetzt wird, 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;

Testcode:

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);
}
Meriton
quelle
Funktioniert die Umkehrung korrekt, wenn die Schleife auf einen anderen Knoten als den ersten zeigt? Wenn die anfängliche verknüpfte Liste wie folgt lautet: 1-> 2-> 3-> 4-> 5-> 2 (mit einem Zyklus von 5 bis 2), sieht die umgekehrte Liste wie folgt aus: 1-> 2 <-3 <-4 <-5? Und wenn das Gegenteil der Fall ist, wird die endgültige rekonstruierte Liste vermasselt?
Zenil
1
@ Zenil: Deshalb habe ich diesen letzten Testfall geschrieben, bei dem der letzte Knoten auf die Mitte der Liste zeigt. Wenn die Rekonstruktion nicht funktionieren würde, würde dieser Test fehlschlagen. Zu Ihrem Beispiel: Die Umkehrung von 1-> 2-> 3-> 5-> 2 wäre 1-> 2-> 5-> 4-> 3-> 2, da die Schleife erst am Ende der Liste stoppt wurde erreicht, nicht wenn das Ende der Schleife (das wir nicht leicht erkennen können) erreicht wurde.
Meriton
28

Schildkröte und Hase

Schauen Sie sich Pollards Rho-Algorithmus an . Es ist nicht ganz das gleiche Problem, aber vielleicht verstehen Sie die Logik daraus und wenden sie auf verknüpfte Listen an.

(Wenn Sie faul sind, können Sie einfach die Zykluserkennung überprüfen - überprüfen Sie den Teil über die Schildkröte und den Hasen.)

Dies erfordert nur eine 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 suchen nicht nach beiden nextund next.nextnach Nullen. Da die Schildkröte immer im Rückstand ist, müssen Sie sie auch nicht auf Null prüfen - der Hase hat das bereits getan.)

Larry
quelle
13

Der Benutzer unicornaddict hat oben einen netten Algorithmus, der jedoch leider einen Fehler für nicht-loopy Listen mit ungerader Länge> = 3 enthält. Das Problem ist, dass er fastkurz vor dem Ende der Liste "stecken bleiben" kann, ihn sloweinholt 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;
    }
}
Carl Mäsak
quelle
10

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

Wenn sich schnell und langsam am Punkt p treffen,

Zurückgelegte Strecke schnell = a + b + c + b = a + 2b + c

Zurückgelegte Strecke langsam = a + b

Da ist das schnelle 2 mal schneller als das langsame. Also a + 2b + c = 2 (a + b) , dann erhalten wir a = c .

Wenn also wieder ein anderer langsamer Zeiger von Kopf nach q läuft, läuft gleichzeitig ein schneller Zeiger von p nach q , sodass sie sich am Punkt q zusammen treffen .

Geben Sie hier die Bildbeschreibung ein

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;
}
Neil
quelle
2
Ein Bild sagt mehr als Tausende von Wörtern. Danke für die nette und einfache Erklärung!
Calios
1
Beste Erklärung im Internet.
Ich
Wenn aes größer als die Schleifenlänge ist, führt fast mehrere Schleifen aus, und die Formel distance (fast) = a + b + b + cändert sich, a + (b+c) * k + bum einen zusätzlichen Parameter einzuführen k, der die Anzahl der von schnell eins erstellten Lopps zählt.
Ben
9

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)
Khaled.K
quelle
Wie ist die Raumkomplexität O (2n)?
Programmer345
@ User3543449 Sie haben Recht, es sollte nur nbehoben sein
Khaled.K
1
Dies ist tatsächlich die Zeit ~ O (n ^ 2), da jede Prüfung für eine ArrayList O (n) enthält und es O (n) von ihnen gibt. Verwenden Sie stattdessen ein HashSet für die lineare Zeit.
Dave L.
3
Dies testet nicht auf Zyklen, sondern auf doppelte Werte unter Verwendung der Elemente equalsund hashCode. Es ist nicht dasselbe. Und es stört nulldas letzte Element. Und die Frage sagte nichts über das Speichern der Knoten in einem LinkedList.
Lii
2
@Lii es ist ein Pseudocode, das ist kein Java-Code, deshalb habe ich ihn mit Algorithm
Khaled.K
8

Das Folgende ist möglicherweise nicht die beste Methode - es ist O (n ^ 2). Es sollte jedoch dazu dienen, die Arbeit (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++;
}
Sparky
quelle
Wie würden Sie wissen, wie viele Elemente in der Liste enthalten sind, um for () auszuführen?
Jethro Larson
@JethroLarson: Der letzte Knoten in einer verknüpften Liste zeigt auf eine bekannte Adresse (in vielen Implementierungen ist dies NULL). Beenden Sie die for-Schleife, wenn diese bekannte Adresse erreicht ist.
Sparky
3
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 denke, dies löst nicht das Problem des konstanten Platzbedarfs ... aber es kommt zumindest in angemessener Zeit dort an, richtig? Es wird nur der Platz der verknüpften Liste plus der Platz einer Menge mit n Elementen benötigt (wobei n die Anzahl der Elemente in der verknüpften Liste oder die Anzahl der Elemente ist, bis eine Schleife erreicht ist). Und für die Zeit würde eine Worst-Case-Analyse meiner Meinung nach O (nlog (n)) vorschlagen. SortedSet-Suchvorgänge für enthält () sind log (n) (überprüfen Sie das Javadoc, aber ich bin mir ziemlich sicher, dass die zugrunde liegende Struktur von TreeSet TreeMap ist, dessen wiederum ein rot-schwarzer Baum ist), und im schlimmsten Fall (keine Schleifen, oder Schleife ganz am Ende), es muss n Nachschlagen machen.

schmähen
quelle
2
Ja, eine Lösung mit einer Art Set funktioniert einwandfrei, benötigt jedoch Platz proportional zur Größe der Liste.
Jjujuma
3

Wenn wir die Klasse einbetten dürfen Node, würde ich das Problem lösen, wie ich es unten implementiert habe. hasLoop()läuft in O (n) Zeit und nimmt nur den Raum von counter. Scheint dies eine angemessene Lösung zu sein? Oder gibt es eine Möglichkeit, dies ohne Einbettung zu tun Node? (Offensichtlich würde es in einer realen Implementierung mehr Methoden wie RemoveNode(Node n)usw. geben.)

public class LinkedNodeList {
    Node first;
    Int count;

    LinkedNodeList(){
        first = null;
        count = 0;
    }

    LinkedNodeList(Node n){
        if (n.next != null){
            throw new error("must start with single node!");
        } else {
            first = n;
            count = 1;
        }
    }

    public void addNode(Node n){
        Node lookingAt = first;

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

        lookingAt.next = n;
        count++;
    }

    public boolean hasLoop(){

        int counter = 0;
        Node lookingAt = first;

        while(lookingAt.next != null){
            counter++;
            if (count < counter){
                return false;
            } else {
               lookingAt = lookingAt.next;
            }
        }

        return true;

    }



    private class Node{
        Node next;
        ....
    }

}
schmähen
quelle
1

Sie können dies sogar in konstanter O (1) -Zeit tun (obwohl dies nicht sehr schnell oder effizient wäre): Es gibt eine begrenzte Anzahl von Knoten, die der Arbeitsspeicher Ihres Computers aufnehmen kann, beispielsweise N Datensätze. Wenn Sie mehr als N Datensätze durchlaufen, haben Sie eine Schleife.

Eduardo
quelle
Dies ist nicht O (1), dieser Algorithmus hat keine bedeutsame zeitliche Komplexität in der Big-O-Notation. Die Big-O-Notation gibt nur Auskunft über die Leistung im Grenzbereich, wenn die Eingabegröße unendlich wird. Also , wenn Ihr Algorithmus auf der Annahme basiert , dass es sind keine Listen mit mehr als N Elemente für einige große N, die Grenze der Laufzeit als die Listengröße gegen unendlich geht nicht definiert ist. Daher ist die Komplexität nicht "O (irgendetwas)".
FGP
1
 // 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;
        }
    }
}
Richa
quelle
1
boolean hasCycle(Node head) {

    boolean dec = false;
    Node first = head;
    Node sec = head;
    while(first != null && sec != null)
    {
        first = first.next;
        sec = sec.next.next;
        if(first == sec )
        {
            dec = true;
            break;
        }

    }
        return dec;
}

Verwenden Sie die obige Funktion, um eine Schleife in der verknüpften Liste in Java zu erkennen.

Aditya Parmar
quelle
2
Fast das gleiche wie meine Antwort oben, hat aber ein Problem. Es wird eine NullPointerException für Listen mit Listen ungerader Länge (ohne Schleifen) ausgelöst. Wenn beispielsweise head.next null ist, löst sec.next.next eine NPE aus.
Dave L.
1

Das Erkennen einer Schleife in einer verknüpften Liste kann auf eine der einfachsten Arten erfolgen, was zu einer O (N) -Komplexität unter Verwendung von Hashmap oder O (NlogN) unter Verwendung eines sortierungsbasierten Ansatzes führt.

Erstellen Sie beim Durchlaufen der Liste ab Kopf eine sortierte Adressliste. Wenn Sie eine neue Adresse einfügen, überprüfen Sie, ob die Adresse bereits in der sortierten Liste vorhanden ist, was die Komplexität von O (logN) erfordert.

Abhinav
quelle
Die Komplexität dieses Ansatzes ist O (N log N)
fgp
0

Ich kann mir keine Möglichkeit vorstellen, dies zeitlich oder räumlich festzuhalten. Beide werden mit der Größe der Liste zunehmen.

Ich würde eine IdentityHashMap verwenden (da es noch kein IdentityHashSet gibt) und jeden Knoten in der Karte speichern. Bevor ein Knoten gespeichert wird, würden Sie includesKey darauf aufrufen. Wenn der Knoten bereits vorhanden ist, haben Sie einen Zyklus.

ItentityHashMap verwendet == anstelle von .equals, damit Sie überprüfen, wo sich das Objekt im Speicher befindet, und nicht, ob es denselben Inhalt hat.

TofuBeer
quelle
3
Es ist sicherlich unmöglich, eine feste Zeit in Anspruch zu nehmen, da sich am Ende der Liste eine Schleife befinden kann, sodass die gesamte Liste besucht werden muss. Der Fast / Slow-Algorithmus demonstriert jedoch eine Lösung mit einer festen Speichermenge.
Dave L.
Bezieht es sich nicht auf sein asymptotisches Verhalten, dh es ist lineares O (n), wobei n die Länge der Liste ist. Behoben wurde O (1)
Mark Robson
0

Ich könnte furchtbar spät und neu sein, um diesen Thread zu bearbeiten. Aber dennoch..

Warum kann die Adresse des Knotens und des "nächsten" Knotens, auf den gezeigt wird, nicht in einer Tabelle gespeichert werden?

Wenn wir so tabellieren könnten

node present: (present node addr) (next node address)

node 1: addr1: 0x100 addr2: 0x200 ( no present node address till this point had 0x200)
node 2: addr2: 0x200 addr3: 0x300 ( no present node address till this point had 0x300)
node 3: addr3: 0x300 addr4: 0x400 ( no present node address till this point had 0x400)
node 4: addr4: 0x400 addr5: 0x500 ( no present node address till this point had 0x500)
node 5: addr5: 0x500 addr6: 0x600 ( no present node address till this point had 0x600)
node 6: addr6: 0x600 addr4: 0x400 ( ONE present node address till this point had 0x400)

Daher wird ein Zyklus gebildet.

Adit Ya
quelle
Ihre Lösung erfüllt nicht die Anforderung "konstanter Speicherplatz".
Arnaud
0

Hier ist mein ausführbarer Code.

Was ich getan habe, ist, die verknüpfte Liste mithilfe von drei temporären Knoten (Raumkomplexität O(1)) zu verehren, die die Verknüpfungen verfolgen.

Die interessante Tatsache dabei ist, den Zyklus in der verknüpften Liste zu erkennen, da Sie im weiteren Verlauf nicht erwarten, zum Startpunkt (Wurzelknoten) zurückzukehren, und einer der temporären Knoten sollte auf Null gehen, es sei denn, Sie einen Zyklus haben, der auf den Wurzelknoten zeigt.

Die zeitliche Komplexität dieses Algorithmus ist O(n)und die räumliche Komplexitä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 von drei Knoten, wobei der letzte Knoten auf den zweiten Knoten zeigt:

    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 von drei Knoten, bei denen der letzte Knoten auf den zweiten Knoten zeigt:

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));
    }
}
Habib Karbasian
quelle
0

Dieser Code ist optimiert und liefert ein schnelleres Ergebnis als der als beste Antwort ausgewählte. Dieser Code erspart Ihnen einen sehr langen Prozess des Verfolgens des Vorwärts- und Rückwärtsknotenzeigers, der im folgenden Fall auftritt, wenn wir dem Besten folgen Antwort 'Methode. Schauen Sie sich den Trockenlauf der folgenden an und Sie werden erkennen, was ich zu sagen versuche. Dann schauen Sie sich das Problem mit der unten angegebenen Methode an und messen Sie die Nr. von Schritten unternommen, 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
}
Sarthak Mehra
quelle
Sind Sie sicher, dass dies in allen Situationen das richtige Ergebnis liefert? Wenn Sie diesen Algorithmus in der Liste 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 3 -> ... ausführen, glaube ich, dass er 4 als Kopf zurückgeben würde, während Sie es wollten 3.
Sunreef
Die Frage ist nur, ob es eine Schleife gibt oder nicht. In diesem Fall funktioniert die Frage absolut einwandfrei und liefert das gewünschte boolesche Ergebnis für den Fall. Wenn Sie den genauen Knoten möchten, von dem aus die Schleife begonnen hat, werden wir es tun Sie müssen dem Code etwas mehr hinzufügen. Was jedoch die Erstellung eines Ergebnisses betrifft, führt dies zu einer schnelleren Schlussfolgerung.
Sarthak Mehra
Sie haben die Frage nicht richtig gelesen: Was ist die beste Schreibweise, boolean hasLoop(Node first)die true zurückgibt, wenn der angegebene Knoten der erste einer Liste mit einer Schleife ist, andernfalls false?
Sunreef
Hier ist der Trockenlauf für Ihre Liste. Der erste Wert bedeutet Rückzeiger und der zweite Teil bedeutet Vorwärtszeiger. (1,1) - (1,3) - (2,3) - (2,5) - (3,5) - (3,7) - (4,7) - (4,4).
Sarthak Mehra
Eigentlich ist mir jetzt klar, dass es zwei Möglichkeiten gibt, die Frage zu verstehen (oder zumindest sehe ich zwei verschiedene Interpretationen). Ihr Algorithmus ist korrekt, wenn Sie nur nach einer Schleife suchen. Aber ich dachte, dass die Frage war, wo die Schleife anfing.
Sunreef
0

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;
}
Irshad ck
quelle
0

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

Dieser Algorithmus kann prüfen, ob eine einfach verknüpfte Liste einen geschlossenen Zyklus hat. Dies kann erreicht werden, indem eine Liste mit zwei Zeigern iteriert wird, die sich mit unterschiedlicher Geschwindigkeit bewegen. Auf diese Weise treffen sich die beiden Zeiger bei einem Zyklus irgendwann in der Zukunft.

Bitte schauen Sie sich meinen Blog-Beitrag in der Datenstruktur der verknüpften Listen an, in dem ich auch ein Code-Snippet mit einer Implementierung des oben genannten Algorithmus in Java-Sprache eingefügt habe.

Grüße,

Andreas (@xnorcode)

xnorcode
quelle
0

Hier ist die Lösung zur Erkennung des Zyklus.

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 
        }
Vishwaraj
quelle
0

// Verknüpfungsfunktion für verknüpfte Listen finden

int findLoop(struct Node* head)
{
    struct Node* slow = head, *fast = head;
    while(slow && fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
            return 1;
    }
 return 0;
}
Sonu Mishra
quelle
-1

Dieser Ansatz hat Platzbedarf, aber eine einfachere Implementierung:

Die Schleife kann durch Speichern von Knoten in einer Karte identifiziert werden. Und bevor Sie den Knoten setzen; Überprüfen Sie, ob der Knoten bereits vorhanden ist. Wenn der Knoten bereits in der Karte vorhanden ist, bedeutet dies, dass die verknüpfte Liste 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;  
  }  
rai.skumar
quelle
Dies entspricht nicht der in der Frage angegebenen konstanten Platzbeschränkung !
Dedek
stimme zu, dass es Platz über dem Kopf hat; Es ist ein weiterer Ansatz, um dieses Problem zu lösen. Der offensichtliche Ansatz ist der Schildkröten- und Harse-Algorithmus.
rai.skumar
@downvoter, es wäre hilfreich, wenn Sie auch den Grund erklären könnten.
Rai.skumar
-2
public boolean isCircular() {

    if (head == null)
        return false;

    Node temp1 = head;
    Node temp2 = head;

    try {
        while (temp2.next != null) {

            temp2 = temp2.next.next.next;
            temp1 = temp1.next;

            if (temp1 == temp2 || temp1 == temp2.next) 
                return true;    

        }
    } catch (NullPointerException ex) {
        return false;

    }

    return false;

}
edst
quelle