Tester une liste liée pour la cyclicité

1. Introduction

Une liste liée individuellement est une séquence de nœuds connectés se terminant par une référence nulle . Cependant, dans certains scénarios, le dernier nœud peut pointer vers un nœud précédent, créant ainsi un cycle.

Dans la plupart des cas, nous voulons pouvoir détecter et être conscients de ces cycles; cet article se concentrera exactement sur cela: détecter et éventuellement supprimer les cycles.

2. Détection d'un cycle

Explorons maintenant quelques algorithmes pour détecter les cycles dans les listes liées.

2.1. Force brute - Complexité temporelle O (n ^ 2)

Avec cet algorithme, nous parcourons la liste en utilisant deux boucles imbriquées. Dans la boucle extérieure, nous traversons un par un. Dans la boucle interne, nous partons de la tête et traversons autant de nœuds que traversés par la boucle externe à ce moment-là.

Si un nœud visité par la boucle externe est visité deux fois par la boucle interne, alors un cycle a été détecté. A l'inverse, si la boucle externe atteint la fin de la liste, cela implique une absence de cycles:

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; }

L'avantage de cette approche est qu'elle nécessite une quantité constante de mémoire. L'inconvénient est que les performances sont très lentes lorsque de grandes listes sont fournies en entrée.

2.2. Hashing - Complexité de l'espace O (n)

Avec cet algorithme, nous maintenons un ensemble de nœuds déjà visités. Pour chaque nœud, nous vérifions s'il existe dans l'ensemble. Sinon, nous l'ajoutons à l'ensemble. L'existence d'un nœud dans l'ensemble signifie que nous avons déjà visité le nœud et fait apparaître la présence d'un cycle dans la liste.

Lorsque nous rencontrons un nœud qui existe déjà dans l'ensemble, nous aurions découvert le début du cycle. Après avoir découvert cela, nous pouvons facilement interrompre le cycle en définissant le champ suivant du nœud précédent sur null , comme illustré ci-dessous:

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; }
    

Dans cette solution, nous avons visité et stocké chaque nœud une fois. Cela équivaut à une complexité temporelle O (n) et une complexité spatiale O (n), ce qui, en moyenne, n'est pas optimal pour les grandes listes.

2.3. Pointeurs rapides et lents

L'algorithme suivant pour trouver des cycles peut être mieux expliqué à l' aide d'une métaphore .

Considérez une piste de course où deux personnes courent. Étant donné que la vitesse de la deuxième personne est le double de celle de la première personne, la deuxième personne fera le tour de la piste deux fois plus vite que la première et rencontrera à nouveau la première personne au début du tour.

Ici, nous utilisons une approche similaire en itérant dans la liste simultanément avec un itérateur lent et un itérateur rapide (vitesse 2x). Une fois que les deux itérateurs sont entrés dans une boucle, ils finiront par se rencontrer à un moment donné.

Par conséquent, si les deux itérateurs se rencontrent à un moment donné, nous pouvons conclure que nous sommes tombés sur un cycle:

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); }

CycleDetectionResult est une classe pratique pour contenir le résultat: une variable booléenne qui indique si le cycle existe ou non et s'il existe, alors cela contient également une référence au point de rencontre à l'intérieur du cycle:

public class CycleDetectionResult { boolean cycleExists; Node node; }

Cette méthode est également connue sous le nom de «l'algorithme de la tortue et du lièvre» ou «l'algorithme de recherche de cycle de Flyods».

3. Suppression de cycles d'une liste

Jetons un coup d'œil à quelques méthodes pour supprimer les cycles. Toutes ces méthodes supposent que «l'algorithme de recherche de cycle Flyods» a été utilisé pour la détection de cycle et s'appuie dessus.

3.1. Force brute

Une fois que les itérateurs rapides et lents se rencontrent à un moment donné du cycle, nous prenons un itérateur supplémentaire (disons ptr ) et le pointons vers la tête de la liste. Nous commençons à itérer la liste avec ptr. A chaque étape, nous vérifions si ptr est joignable depuis le point de rendez-vous.

Cela se termine lorsque ptr atteint le début de la boucle car c'est le premier point lorsqu'il entre dans la boucle et devient accessible à partir du point de rencontre.

Une fois le début de la boucle ( bg ) découvert, alors il est trivial de trouver la fin du cycle (nœud dont le champ suivant pointe vers bg ). Le pointeur suivant de ce nœud d'extrémité est alors mis à null pour supprimer le cycle:

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; } }

Malheureusement, cet algorithme fonctionne également mal en cas de grandes listes et de grands cycles, car nous devons parcourir le cycle plusieurs fois.

3.2. Solution optimisée - Comptage des nœuds de boucle

Définissons d'abord quelques variables:

  • n = la taille de la liste
  • k = la distance entre la tête de la liste et le début du cycle
  • l = la taille du cycle

Nous avons la relation suivante entre ces variables:

k + l = n

Nous utilisons cette relation dans cette approche. Plus particulièrement, lorsqu'un itérateur qui commence au début de la liste, a déjà parcouru l nœuds, alors il doit parcourir k nœuds supplémentaires pour atteindre la fin de la liste.

Voici le contour de l'algorithme:

  1. Une fois que les itérateurs rapides et lents se rencontrent, trouvez la durée du cycle. Cela peut être fait en gardant l'un des itérateurs en place tout en continuant l'autre itérateur (itération à vitesse normale, un par un) jusqu'à ce qu'il atteigne le premier pointeur, en conservant le nombre de nœuds visités. Cela compte comme 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.

Enfin, nous avons également montré trois méthodes pour supprimer un cycle, une fois qu'il est détecté à l'aide de «l'algorithme de recherche de cycle Flyods».

L'exemple de code complet est disponible à l'adresse over sur Github.