Testen Sie eine verknüpfte Liste auf Zyklizität

1. Einleitung

Eine einfach verknüpfte Liste ist eine Folge verbundener Knoten, die mit einer Nullreferenz enden . In einigen Szenarien kann der letzte Knoten jedoch auf einen vorherigen Knoten verweisen, wodurch effektiv ein Zyklus erstellt wird.

In den meisten Fällen möchten wir in der Lage sein, diese Zyklen zu erkennen und zu kennen. Dieser Artikel konzentriert sich genau darauf - das Erkennen und potenzielle Entfernen von Zyklen.

2. Erkennen eines Zyklus

Lassen Sie uns nun einige Algorithmen zum Erkennen von Zyklen in verknüpften Listen untersuchen.

2.1. Brute Force - O (n ^ 2) Zeitkomplexität

Mit diesem Algorithmus durchlaufen wir die Liste mit zwei verschachtelten Schleifen. In der äußeren Schleife durchlaufen wir eins nach dem anderen. In der inneren Schleife beginnen wir am Kopf und durchlaufen so viele Knoten, wie zu diesem Zeitpunkt von der äußeren Schleife durchlaufen wurden.

Wenn ein Knoten, der von der äußeren Schleife besucht wird, zweimal von der inneren Schleife besucht wird, wurde ein Zyklus erkannt. Wenn umgekehrt die äußere Schleife das Ende der Liste erreicht, bedeutet dies, dass keine Zyklen vorhanden sind:

public static  boolean detectCycle(Node head) { if (head == null) { return false; } Node it1 = head; int nodesTraversedByOuter = 0; while (it1 != null && it1.next != null) { it1 = it1.next; nodesTraversedByOuter++; int x = nodesTraversedByOuter; Node it2 = head; int noOfTimesCurrentNodeVisited = 0; while (x > 0) { it2 = it2.next; if (it2 == it1) { noOfTimesCurrentNodeVisited++; } if (noOfTimesCurrentNodeVisited == 2) { return true; } x--; } } return false; }

Der Vorteil dieses Ansatzes besteht darin, dass eine konstante Speichermenge erforderlich ist. Der Nachteil ist, dass die Leistung sehr langsam ist, wenn große Listen als Eingabe bereitgestellt werden.

2.2. Hashing - O (n) Raumkomplexität

Mit diesem Algorithmus pflegen wir eine Reihe bereits besuchter Knoten. Für jeden Knoten prüfen wir, ob er in der Menge vorhanden ist. Wenn nicht, fügen wir es dem Set hinzu. Das Vorhandensein eines Knotens in der Menge bedeutet, dass wir den Knoten bereits besucht haben, und weist auf das Vorhandensein eines Zyklus in der Liste hin.

Wenn wir auf einen Knoten stoßen, der bereits in der Menge vorhanden ist, hätten wir den Beginn des Zyklus entdeckt. Nachdem wir dies festgestellt haben, können wir den Zyklus leicht unterbrechen, indem wir das nächste Feld des vorherigen Knotens auf null setzen , wie unten gezeigt:

public static  boolean detectCycle(Node head) { if (head == null) { return false; } Set
    
      set = new HashSet(); Node node = head; while (node != null) { if (set.contains(node)) { return true; } set.add(node); node = node.next; } return false; }
    

In dieser Lösung haben wir jeden Knoten einmal besucht und gespeichert. Dies entspricht einer O (n) -Zeitkomplexität und einer O (n) -Raumkomplexität, die im Durchschnitt für große Listen nicht optimal ist.

2.3. Schnelle und langsame Zeiger

Der folgende Algorithmus zum Finden von Zyklen kann am besten mit einer Metapher erklärt werden .

Stellen Sie sich eine Rennstrecke vor, auf der zwei Personen Rennen fahren. Da die Geschwindigkeit der zweiten Person doppelt so hoch ist wie die der ersten Person, fährt die zweite Person doppelt so schnell um die Strecke wie die erste und trifft die erste Person zu Beginn der Runde wieder.

Hier verwenden wir einen ähnlichen Ansatz, indem wir die Liste gleichzeitig mit einem langsamen und einem schnellen Iterator (2x Geschwindigkeit) durchlaufen. Sobald beide Iteratoren eine Schleife betreten haben, treffen sie sich schließlich an einem Punkt.

Wenn sich die beiden Iteratoren zu irgendeinem Zeitpunkt treffen, können wir daraus schließen, dass wir auf einen Zyklus gestoßen sind:

public static  CycleDetectionResult detectCycle(Node head) { if (head == null) { return new CycleDetectionResult(false, null); } Node slow = head; Node fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) { return new CycleDetectionResult(true, fast); } } return new CycleDetectionResult(false, null); }

Wenn CycleDetectionResult eine Convenience-Klasse ist, die das Ergebnis enthält: Eine boolesche Variable, die angibt, ob ein Zyklus vorhanden ist oder nicht, und falls vorhanden, enthält diese auch einen Verweis auf den Treffpunkt innerhalb des Zyklus:

public class CycleDetectionResult { boolean cycleExists; Node node; }

Diese Methode wird auch als "The Tortoise and The Hare Algorithm" oder "Flyods Cycle Finding Algorithm" bezeichnet.

3. Entfernen von Zyklen aus einer Liste

Schauen wir uns einige Methoden zum Entfernen von Zyklen an. Alle diese Methoden setzen voraus, dass der 'Flyods Cycle-Finding-Algorithmus' zur Zykluserkennung verwendet wurde und darauf aufbaut.

3.1. Rohe Gewalt

Sobald sich der schnelle und der langsame Iterator an einem Punkt im Zyklus treffen, nehmen wir einen weiteren Iterator (z. B. ptr ) und zeigen ihn auf den Kopf der Liste. Wir beginnen die Liste mit ptr zu iterieren. Bei jedem Schritt prüfen wir, ob ptr vom Treffpunkt aus erreichbar ist.

Dies endet, wenn ptr den Anfang der Schleife erreicht, da dies der erste Punkt ist, an dem es in die Schleife eintritt und vom Treffpunkt aus erreichbar wird.

Sobald der Beginn der Schleife ( bg ) entdeckt ist, ist es trivial, das Ende des Zyklus zu finden (Knoten, dessen nächstes Feld auf bg zeigt ). Der nächste Zeiger dieses Endknotens wird dann auf Null gesetzt , um den Zyklus zu entfernen:

public class CycleRemovalBruteForce { private static  void removeCycle( Node loopNodeParam, Node head) { Node it = head; while (it != null) { if (isNodeReachableFromLoopNode(it, loopNodeParam)) { Node loopStart = it; findEndNodeAndBreakCycle(loopStart); break; } it = it.next; } } private static  boolean isNodeReachableFromLoopNode( Node it, Node loopNodeParam) { Node loopNode = loopNodeParam; do { if (it == loopNode) { return true; } loopNode = loopNode.next; } while (loopNode.next != loopNodeParam); return false; } private static  void findEndNodeAndBreakCycle( Node loopStartParam) { Node loopStart = loopStartParam; while (loopStart.next != loopStartParam) { loopStart = loopStart.next; } loopStart.next = null; } }

Leider funktioniert dieser Algorithmus auch bei großen Listen und großen Zyklen schlecht, da wir den Zyklus mehrmals durchlaufen müssen.

3.2. Optimierte Lösung - Zählen der Schleifenknoten

Definieren wir zunächst einige Variablen:

  • n = die Größe der Liste
  • k = der Abstand vom Kopf der Liste bis zum Beginn des Zyklus
  • l = die Größe des Zyklus

Wir haben die folgende Beziehung zwischen diesen Variablen:

k + l = n

Wir nutzen diese Beziehung in diesem Ansatz. Insbesondere wenn ein Iterator, der von Anfang an von der Liste beginnt, schon bereist hat l Knoten, dann hat es zu reisen k mehr Knoten das Ende der Liste zu erreichen.

Hier ist die Gliederung des Algorithmus:

  1. Sobald sich schnelle und langsame Iteratoren treffen, ermitteln Sie die Länge des Zyklus. Dies kann erreicht werden, indem einer der Iteratoren an Ort und Stelle gehalten wird, während der andere Iterator (Iteration mit normaler Geschwindigkeit nacheinander) fortgesetzt wird, bis er den ersten Zeiger erreicht, wobei die Anzahl der besuchten Knoten beibehalten wird. Dies zählt als l
  2. Take two iterators (ptr1 and ptr2) at the beginning of the list. Move one of the iterator (ptr2) l steps
  3. Now iterate both the iterators until they meet at the start of the loop, subsequently, find the end of the cycle and point it to null

This works because ptr1 is k steps away from the loop, and ptr2, which is advanced by l steps, also needs k steps to reach the end of the loop (n – l = k).

And here's a simple, potential implementation:

public class CycleRemovalByCountingLoopNodes { private static  void removeCycle( Node loopNodeParam, Node head) { int cycleLength = calculateCycleLength(loopNodeParam); Node cycleLengthAdvancedIterator = head; Node it = head; for (int i = 0; i < cycleLength; i++) { cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } while (it.next != cycleLengthAdvancedIterator.next) { it = it.next; cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } cycleLengthAdvancedIterator.next = null; } private static  int calculateCycleLength( Node loopNodeParam) { Node loopNode = loopNodeParam; int length = 1; while (loopNode.next != loopNodeParam) { length++; loopNode = loopNode.next; } return length; } }

Next, let's focus on a method in which we can even eliminate the step of calculating the loop length.

3.3. Optimized Solution – Without Counting the Loop Nodes

Let's compare the distances traveled by the fast and slow pointers mathematically.

For that, we need a few more variables:

  • y = distance of the point where the two iterators meet, as seen from the beginning of the cycle
  • z = distance of the point where the two iterators meet, as seen from the end of the cycle (this is also equal to l – y)
  • m = number of times the fast iterator completed the cycle before the slow iterator enters the cycle

Keeping the other variables same as defined in the previous section, the distance equations will be defined as:

  • Distance traveled by slow pointer = k (distance of cycle from head) + y (meeting point inside cycle)
  • Distance traveled by fast pointer = k (distance of cycle from head) + m (no of times fast pointer completed the cycle before slow pointer enters) * l (cycle length) + y (meeting point inside cycle)

We know that distance traveled by the fast pointer is twice that of the slow pointer, hence:

k + m * l + y = 2 * (k + y)

which evaluates to:

y = m * l – k

Subtracting both sides from l gives:

l – y = l – m * l + k

or equivalently:

k = (m – 1) * l + z (where, l – y is z as defined above)

This leads to:

k = (m – 1) Full loop runs + An extra distance z

In other words, if we keep one iterator at the head of the list and one iterator at the meeting point, and move them at the same speed, then, the second iterator will complete m – 1 cycles around the loop and meet the first pointer at the beginning of the cycle. Using this insight we can formulate the algorithm:

  1. Use ‘Flyods Cycle-Finding Algorithm' to detect the loop. If loop exists, this algorithm would end at a point inside the loop (call this the meeting point)
  2. Take two iterators, one at the head of the list (it1) and one at the meeting point (it2)
  3. Traverse both iterators at the same speed
  4. Since the distance of the loop from head is k (as defined above), the iterator started from head would reach the cycle after k steps
  5. In k steps, iterator it2 would traverse m – 1 cycles of the loop and an extra distance z. Since this pointer was already at a distance of z from the beginning of the cycle, traversing this extra distance z, would bring it also at the beginning of the cycle
  6. Both the iterators meet at the beginning of the cycle, subsequently, we can find the end of the cycle and point it to null

This can be implemented:

public class CycleRemovalWithoutCountingLoopNodes { private static  void removeCycle( Node meetingPointParam, Node head) { Node loopNode = meetingPointParam; Node it = head; while (loopNode.next != it.next) { it = it.next; loopNode = loopNode.next; } loopNode.next = null; } }

This is the most optimized approach for detection and removal of cycles from a linked list.

4. Conclusion

In this article, we described various algorithms for detecting a cycle in a list. We looked into algorithms with different computing time and memory space requirements.

Schließlich haben wir drei Methoden gezeigt, um einen Zyklus zu entfernen, sobald er mithilfe des 'Flyods Cycle-Finding-Algorithmus' erkannt wurde.

Das vollständige Codebeispiel ist auf Github verfügbar.