wake-up-neo.com

Was ist ein effizienter Algorithmus, um festzustellen, ob eine einzeln verknüpfte Liste zirkulär/zyklisch ist oder nicht?

Wie kann ich feststellen, ob eine einzeln verknüpfte Liste zirkulär/zyklisch ist oder nicht? Ich habe versucht zu suchen, konnte aber keine zufriedenstellende Lösung finden. Können Sie nach Möglichkeit eine Pseudocode- oder Java-Implementierung bereitstellen?

Zum Beispiel:
135714575, wobei der zweite 5 tatsächlich das dritte Element der Liste ist.

36
harshit

Die Standardantwort lautet, zwei Iteratoren am Anfang zu nehmen, den ersten einmal zu erhöhen und den zweiten zweimal. Prüfen Sie, ob sie auf dasselbe Objekt zeigen. Wiederholen Sie diesen Vorgang, bis derjenige, der zweimal inkrementiert wird, entweder den ersten trifft oder das Ende erreicht.

Dieser Algorithmus findet jede zirkuläre Verknüpfung in der Liste, nicht nur, dass es sich um einen vollständigen Kreis handelt.

Pseudo-Code (nicht Java, ungeprüft - von meinem Kopf weg)

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
   }
}
76
Lou Franco

Ein einfacher Algorithmus namens Floyd-Algorithmus soll zwei Zeiger a und b haben, die beide beim ersten Element der verknüpften Liste beginnen. Dann erhöhen Sie bei jedem Schritt a einmal und b zweimal. Wiederholen Sie diesen Vorgang, bis Sie entweder das Ende der Liste (keine Schleife) oder a == b (die verknüpfte Liste enthält eine Schleife) erreicht haben.

Ein anderer Algorithmus ist Brent-Algorithmus .

14
Mark Byers

Drei Hauptstrategien, die ich kenne:

  1. Beginnen Sie mit dem Durchsuchen der Liste und verfolgen Sie alle Knoten, die Sie besucht haben (speichern Sie beispielsweise ihre Adressen in einer Karte). Überprüfen Sie bei jedem neuen Knoten, den Sie besuchen. Wenn Sie den Knoten bereits besucht haben, gibt es offensichtlich eine Schleife. Wenn es keine Schleife gibt, erreichen Sie schließlich das Ende. Das ist nicht so toll, da es um die Komplexität O(N) zum Speichern der zusätzlichen Informationen geht.

  2. Die Schildkröten-/Hasenlösung. Beginnen Sie zwei Zeiger an der Spitze der Liste. Der erste Zeiger, die "Schildkröte", bewegt sich bei jeder Wiederholung um einen Knoten vorwärts. Der andere Zeiger, der "Hase", bewegt sich bei jeder Wiederholung um zwei Knoten vorwärts. Wenn es keine Schleife gibt, erreichen der Hase und die Schildkröte beide das Ende der Liste. Wenn es eine Schleife gibt, passiert der Hase irgendwann die Schildkröte und wenn das passiert, wissen Sie, dass es eine Schleife gibt. Dies ist O(1) - Raumkomplexität und ein ziemlich einfacher Algorithmus.

  3. Verwenden Sie den Algorithmus, um eine verknüpfte Liste umzukehren. Wenn die Liste eine Schleife hat, landen Sie wieder am Anfang der Liste, während Sie versuchen, sie umzukehren. Wenn keine Schleife vorhanden ist, ist das Umkehren beendet und das Ende erreicht. Dies ist O(1) - Raumkomplexität, aber ein etwas hässlicherer Algorithmus.

8

Ich zähle deine Knoten und komme wieder zum * Kopf.

4
Batman

Verwenden Sie den Tortoise-Hare-Algorithmus .

2
leppie

Wie wäre es mit folgendem Ansatz:

Sortieren Sie die Linkliste in aufsteigender Reihenfolge, indem Sie einem beliebigen Standardalgorithmus folgen. Vor dem Sortieren: 4-2-6-1-5 Nach dem Sortieren: 1-2-4-5-6

Überprüfen Sie nach dem Sortieren die einzelnen Knotendaten und vergleichen Sie sie mit den Daten des Link-Knotens.

if (currentcode-> data> currentnode-> link-> data) d. h. kreisförmig = wahr;

Wenn bei einem beliebigen Vergleich "currentnode-> data" für eine sortierte Linkliste größer als "currentcode-> link-> data" ist, bedeutet dies, dass der aktuelle Knoten auf einen vorherigen Knoten (d. H. Zirkulär) zeigt.

Jungs, ich habe kein Setup, um den Code zu testen. Lassen Sie mich jetzt wissen, ob dieses Konzept funktioniert.

2
newbie

Ein Algorithmus ist:

  1. Speichern Sie den Zeiger auf den ersten Knoten
  2. Durchlaufen Sie die Liste und vergleichen Sie jeden Knotenzeiger mit diesem Zeiger
  3. Wenn Sie auf einen NULL-Zeiger stoßen, ist die Liste nicht zirkulär verknüpft
  4. Wenn Sie beim ersten Durchlauf auf den ersten Knoten stoßen, handelt es sich um eine kreisförmig verknüpfte Liste
1
Asha

Hier ist eine schöne Seite, auf der die verschiedenen Lösungen kopiert werden können.

Findet die einfach verknüpfte Liste

Dies ist der Gewinner auf dieser Seite

// Best solution
function boolean hasLoop(Node startNode){
  Node slowNode = Node fastNode1 = Node fastNode2 = startNode;
  while (slowNode && fastNode1 = fastNode2.next() && fastNode2 = fastNode1.next()){
    if (slowNode == fastNode1 || slowNode == fastNode2) return true;
    slowNode = slowNode.next();
  }
  return false;
}

Diese Lösung ist "Floyds Cycle-Finding Algorithm", wie von Robert W. Floyd 1967 In "Non-deterministic Algorithms" veröffentlicht. Es ist auch genannt "Die Schildkröte und der Hase Algorithmus".

0
Markus Lausberg

Beginnen Sie an einem Knoten und zeichnen Sie ihn auf, und wiederholen Sie die gesamte Liste, bis Sie einen Nullzeiger oder den Knoten, mit dem Sie begonnen haben, erreichen.

So etwas wie:

Node start = list->head;
Node temp = start->next;
bool circular = false;
while(temp != null && temp != start)
{
   if(temp == start)
   {
     circular = true;
     break;
   }
   temp = temp->next;
}
return circular

Dies ist O (n), was so ziemlich das Beste ist, das Sie mit einer einzeln verknüpften Liste erhalten können (korrigieren Sie mich, wenn ich falsch liege).

Um Zyklen in der Liste zu finden (z. B. in der Mitte), können Sie Folgendes tun:

Node[] array; // Use a vector or ArrayList to support dynamic insertions
Node temp = list->head;
bool circular = false;
while(temp != null)
{
   if(array.contains(temp) == true)
   {
     circular = true;
     break;
   }
   array.insert(temp);
   temp = temp->next;
}
return circular

Dies wird aufgrund der Einfügungszeiten dynamischer Arrays etwas langsamer sein.

0
samoz

Versuche dies 

/* Link list Node */

struct Node { int data; struct Node * next; };

/ * Diese Funktion gibt true zurück, wenn die verknüpfte Liste Zirkulär ist, andernfalls false. */ bool isCircular (struct Node * head) { // Eine leere verknüpfte Liste ist kreisförmig if (head == NULL) wahr zurückgeben;

// Next of head
struct Node *node = head->next;

// This loop would stope in both cases (1) If
// Circular (2) Not circular
while (node != NULL && node != head)
   node = node->next;

// If loop stopped because of circular
// condition
return (node == head);

}

0
Dwivedi Ji

@samoz hat aus meiner Sicht die Antwort! Pseudocode fehlt. Wäre so etwas

ihre Liste ist Ihre verknüpfte Liste

allnodes = hashmap
while yourlist.hasNext()
   node = yourlist.next()
   if(allnodes.contains(node))
      syso "loop found"
      break;
   hashmap.add(node)

entschuldigung, der Code ist sehr pseudo (mehr Scripting als Java in letzter Zeit)

0
leo

Es wird niemals von der Schleife beendet, es kann auch in der folgenden Lösung ausgeführt werden:

bool hasCircle(List l)
{
   Iterator i = l.begin(), j = l.begin();
   while (true) {
      // increment the iterators, if either is at the end, you're done, no circle
      if (i.hasNext())  i = i.next(); else return false;

      // second iterator is travelling twice as fast as first
      if (j.hasNext())  j = j.next(); else return false;
      if (j.hasNext())  j = j.next(); else return false;

      // this should be whatever test shows that the two
      // iterators are pointing at the same place
      if (i.getObject() == j.getObject()) { 
          return true;
      } 
      if(i.next()==j)
          break;
    }
}
0
ajay