Testare un elenco collegato per la ciclicità

1. Introduzione

Un elenco collegato singolarmente è una sequenza di nodi connessi che termina con un riferimento nullo . Tuttavia, in alcuni scenari, l'ultimo nodo potrebbe puntare a un nodo precedente, creando effettivamente un ciclo.

Nella maggior parte dei casi, vogliamo essere in grado di rilevare ed essere consapevoli di questi cicli; questo articolo si concentrerà esattamente su questo: rilevare e potenzialmente rimuovere i cicli.

2. Rilevamento di un ciclo

Esploriamo ora un paio di algoritmi per rilevare i cicli negli elenchi collegati.

2.1. Forza bruta - O (n ^ 2) Complessità temporale

Con questo algoritmo, attraversiamo l'elenco utilizzando due cicli annidati. Nel ciclo esterno, attraversiamo uno per uno. Nel loop interno, partiamo dalla testa e attraversiamo tanti nodi quanti sono stati attraversati dal loop esterno in quel momento.

Se un nodo visitato dal loop esterno viene visitato due volte dal loop interno, è stato rilevato un ciclo. Al contrario, se il ciclo esterno raggiunge la fine della lista, ciò implica un'assenza di cicli:

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

Il vantaggio di questo approccio è che richiede una quantità di memoria costante. Lo svantaggio è che le prestazioni sono molto lente quando vengono forniti elenchi di grandi dimensioni come input.

2.2. Hashing - O (n) Space Complexity

Con questo algoritmo, manteniamo un insieme di nodi già visitati. Per ogni nodo, controlliamo se esiste nell'insieme. In caso contrario, lo aggiungiamo al set. L'esistenza di un nodo nell'insieme significa che abbiamo già visitato il nodo e anticipa la presenza di un ciclo nell'elenco.

Quando incontriamo un nodo che già esiste nell'insieme, avremmo scoperto l'inizio del ciclo. Dopo aver scoperto questo, possiamo facilmente interrompere il ciclo impostando il campo successivo del nodo precedente su null , come mostrato di seguito:

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 questa soluzione, abbiamo visitato e memorizzato ogni nodo una volta. Ciò equivale a complessità temporale O (n) e complessità spazio O (n), che, in media, non è ottimale per elenchi di grandi dimensioni.

2.3. Puntatori veloci e lenti

Il seguente algoritmo per trovare i cicli può essere spiegato meglio usando una metafora .

Considera una pista in cui due persone corrono. Dato che la velocità della seconda persona è doppia rispetto a quella della prima persona, la seconda persona percorrerà la pista due volte più veloce della prima e incontrerà nuovamente la prima persona all'inizio del giro.

Qui usiamo un approccio simile iterando l'elenco simultaneamente con un iteratore lento e un iteratore veloce (velocità 2x). Una volta che entrambi gli iteratori sono entrati in un ciclo, alla fine si incontreranno in un punto.

Quindi, se i due iteratori si incontrano in qualsiasi punto, possiamo concludere che siamo incappati in un ciclo:

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

Dove CycleDetectionResult è una classe di convenienza per contenere il risultato: una variabile booleana che dice se il ciclo esiste o meno e se esiste, allora questo contiene anche un riferimento al punto di incontro all'interno del ciclo:

public class CycleDetectionResult { boolean cycleExists; Node node; }

Questo metodo è noto anche come "Algoritmo della tartaruga e della lepre" o "Algoritmo di ricerca del ciclo di Flyods".

3. Rimozione di cicli da un elenco

Diamo un'occhiata ad alcuni metodi per rimuovere i cicli. Tutti questi metodi presumono che l '"algoritmo di ricerca del ciclo di Flyods" sia stato utilizzato per il rilevamento del ciclo e si basa su di esso.

3.1. Forza bruta

Una volta che gli iteratori veloci e lenti si incontrano in un punto del ciclo, prendiamo un altro iteratore (diciamo ptr ) e lo puntiamo all'inizio della lista. Iniziamo a iterare l'elenco con ptr. Ad ogni passaggio, controlliamo se ptr è raggiungibile dal punto di incontro.

Questo termina quando ptr raggiunge l'inizio del loop perché quello è il primo punto in cui entra nel loop e diventa raggiungibile dal punto di incontro.

Una volta scoperto l'inizio del ciclo ( bg ), è banale trovare la fine del ciclo (nodo il cui campo successivo punta a bg ). Il puntatore successivo di questo nodo finale viene quindi impostato su null per rimuovere il ciclo:

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

Sfortunatamente, questo algoritmo funziona male anche in caso di elenchi di grandi dimensioni e cicli di grandi dimensioni, perché dobbiamo attraversare il ciclo più volte.

3.2. Soluzione ottimizzata: conteggio dei nodi del loop

Definiamo prima alcune variabili:

  • n = la dimensione dell'elenco
  • k = la distanza dall'inizio della lista all'inizio del ciclo
  • l = la dimensione del ciclo

Abbiamo la seguente relazione tra queste variabili:

k + l = n

Utilizziamo questa relazione in questo approccio. Più in particolare, quando un iteratore che inizia dall'inizio della lista, ha già percorso l nodi, allora deve percorrere altri k nodi per raggiungere la fine della lista.

Ecco lo schema dell'algoritmo:

  1. Una volta che gli iteratori veloci e lenti si incontrano, trova la lunghezza del ciclo. Questo può essere fatto mantenendo uno degli iteratori in posizione mentre si continua con l'altro iteratore (iterando a velocità normale, uno per uno) fino a raggiungere il primo puntatore, mantenendo il conteggio dei nodi visitati. Questo conta come 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.

Infine, abbiamo anche mostrato tre metodi per rimuovere un ciclo, una volta rilevato utilizzando l '"algoritmo di ricerca del ciclo di Flyods".

L'esempio di codice completo è disponibile su Github.