streamalism.org

1. Inleiding

Een enkelvoudig gekoppelde lijst is een reeks verbonden knooppunten die eindigt op een nul referentie. In sommige scenario's kan het laatste knooppunt echter naar een vorig knooppunt wijzen, waardoor er in feite een cyclus ontstaat.

In de meeste gevallen willen we deze cycli kunnen detecteren en er bewust van zijn; dit artikel zal precies daarop focussen: het detecteren en mogelijk verwijderen van cycli.

2. Detectie van een cyclus

Laten we nu een aantal algoritmen onderzoeken voor het detecteren van cycli in gekoppelde lijsten.

2.1. Brute Force - O (n ^ 2) Tijdscomplexiteit

Met dit algoritme doorlopen we de lijst met behulp van twee geneste lussen. In de buitenste lus doorkruisen we één voor één. In de binnenste lus beginnen we bij het hoofd en doorlopen we tegen die tijd zoveel knooppunten als de buitenste lus heeft doorlopen.

Als een knooppunt dat wordt bezocht door de buitenlus twee keer wordt bezocht door de binnenlus, dan is er een cyclus gedetecteerd. Omgekeerd, als de buitenste lus het einde van de lijst bereikt, betekent dit dat er geen cycli zijn:

openbare statische boolean detectCycle (Node head) {if (head == null) {return false; } Node it1 = head; int knooppuntenTraversedByOuter = 0; while (it1! = null && it1.next! = null) {it1 = it1.next; knooppuntenTraversedByOuter ++; int x = knooppuntenTraversedByOuter; Knoop it2 = hoofd; int noOfTimesCurrentNodeVisited = 0; while (x> 0) {it2 = it2.next; if (it2 == it1) {noOfTimesCurrentNodeVisited ++; } if (noOfTimesCurrentNodeVisited == 2) {return true; } x--; }} return false; }

Het voordeel van deze benadering is dat er een constante hoeveelheid geheugen nodig is. Het nadeel is dat de performance erg traag is als er grote lijsten als input worden aangeleverd.

2.2. Hashing - O (n) Ruimtecomplexiteit

Met dit algoritme onderhouden we een reeks reeds bezochte knooppunten. Voor elk knooppunt controleren we of het in de set bestaat. Zo niet, dan voegen we het toe aan de set. Het bestaan ​​van een knooppunt in de set betekent dat we het knooppunt al hebben bezocht en brengt de aanwezigheid van een cyclus in de lijst naar voren.

Als we een knooppunt tegenkomen dat al in de set bestaat, zouden we het begin van de cyclus hebben ontdekt. Nadat we dit hebben ontdekt, kunnen we de cyclus gemakkelijk doorbreken door de De volgende veld van het vorige knooppunt naar nul, zoals hieronder aangetoond:

openbare statische boolean detectCycle (Node head) {if (head == null) {return false; } Instellen set = nieuwe HashSet (); Knooppunt knooppunt = hoofd; while (node! = null) {if (set.contains (node)) {return true; } set.add (knooppunt); knooppunt = knooppunt.volgende; } return false; }

In deze oplossing hebben we elk knooppunt één keer bezocht en opgeslagen. Dit komt neer op O (n) tijdcomplexiteit en O (n) ruimtecomplexiteit, die gemiddeld niet optimaal is voor grote lijsten.

2.3. Snelle en langzame wijzers

Het volgende algoritme voor het vinden van cycli kan het beste worden uitgelegd met behulp van een metafoor.

Overweeg een racebaan waar twee mensen racen. Aangezien de snelheid van de tweede persoon het dubbele is van die van de eerste persoon, zal de tweede persoon twee keer zo snel over de baan gaan als de eerste en de eerste persoon aan het begin van de ronde weer ontmoeten.

Hier gebruiken we een vergelijkbare benadering door de lijst tegelijkertijd te herhalen met een langzame iterator en een snelle iterator (2x snelheid). Als beide iteratoren eenmaal in een lus zijn gekomen, zullen ze elkaar uiteindelijk op een bepaald punt ontmoeten.

Als de twee iteratoren elkaar op enig moment ontmoeten, kunnen we dus concluderen dat we op een cyclus zijn gestuit:

openbare statische CycleDetectionResult detectCycle (Node head) {if (head == null) {return new CycleDetectionResult (false, null); } Knooppunt traag = hoofd; Knooppunt snel = hoofd; while (fast! = null && fast.next! = null) {slow = slow.next; fast = fast.next.next; if (slow == fast) {return new CycleDetectionResult (true, fast); }} retourneer nieuwe CycleDetectionResult (false, null); }

Waar CycleDetectionResult is een gemaksklasse om het resultaat te bevatten: a boolean variabele die zegt of een cyclus bestaat of niet en of deze bestaat, dan bevat deze ook een verwijzing naar het ontmoetingspunt binnen de cyclus:

openbare klasse CycleDetectionResult {boolean cycleExists; Knooppunt; }

Deze methode staat ook bekend als het ‘The Tortoise and The Hare Algorithm 'of‘ Flyods Cycle-Finding Algorithm'.

3. Verwijderen van cycli uit een lijst

Laten we een paar methoden bekijken om cycli te verwijderen. Al deze methoden gaan ervan uit dat het ‘Flyods Cycle-Finding Algorithm 'werd gebruikt voor cyclusdetectie en daar bovenop werd gebouwd.

3.1. Brute kracht

Zodra de snelle en de langzame iterator elkaar op een punt in de cyclus ontmoeten, nemen we nog een iterator (bijvoorbeeld ptr) en wijs het naar de kop van de lijst. We beginnen de lijst te herhalen met ptr. Bij elke stap controleren we of ptr is bereikbaar vanaf het ontmoetingspunt.

Dit eindigt wanneer ptr bereikt het begin van de lus omdat dat het eerste punt is wanneer het de lus binnengaat en bereikbaar wordt vanaf het ontmoetingspunt.

Zodra het begin van de lus (bg) wordt ontdekt, dan is het triviaal om het einde van de cyclus te vinden (knooppunt waarvan het volgende veld verwijst naar bg). De volgende wijzer van dit eindknooppunt wordt dan ingesteld op nul om de cyclus te verwijderen:

openbare klasse CycleRemovalBruteForce {privé statische leegte removeCycle (Node loopNodeParam, Node head) {Node it = head; while (it! = null) {if (isNodeReachableFromLoopNode (it, loopNodeParam)) {Node loopStart = it; findEndNodeAndBreakCycle (loopStart); breken; } it = it.next; }} privé statische boolean isNodeReachableFromLoopNode (Node it, Node loopNodeParam) {Node loopNode = loopNodeParam; do {if (it == loopNode) {return true; } loopNode = loopNode.next; } while (loopNode.next! = loopNodeParam); teruggeven false; } privé statische leegte findEndNodeAndBreakCycle (knooppunt loopStartParam) {knooppunt loopStart = loopStartParam; while (loopStart.next! = loopStartParam) {loopStart = loopStart.next; } loopStart.next = null; }}

Helaas presteert dit algoritme ook slecht in het geval van grote lijsten en grote cycli, omdat we de cyclus meerdere keren moeten doorlopen.

3.2. Geoptimaliseerde oplossing - De lusknooppunten tellen

Laten we eerst een paar variabelen definiëren:

• n = de grootte van de lijst
• k = de afstand van het begin van de lijst tot het begin van de cyclus
• l = de grootte van de cyclus

We hebben de volgende relatie tussen deze variabelen:

k + l = n

Bij deze aanpak maken we gebruik van deze relatie. Meer in het bijzonder wanneer een iterator die begint vanaf het begin van de lijst, al is gereisd l knooppunten, dan moet het reizen k meer knooppunten om het einde van de lijst te bereiken.

Hier is het overzicht van het algoritme:

1. Zodra snelle en langzame iteratoren elkaar ontmoeten, zoek dan de lengte van de cyclus. Dit kan worden gedaan door een van de iteratoren op zijn plaats te houden terwijl de andere iterator wordt voortgezet (itererend op normale snelheid, één voor één) totdat deze de eerste wijzer bereikt, waarbij het aantal bezochte knooppunten wordt bijgehouden. Dit geldt als l
2. Neem twee iterators (ptr1 en ptr2) aan het begin van de lijst. Verplaats een van de iteratoren (ptr2) l stappen
3. Herhaal nu beide iteratoren totdat ze elkaar ontmoeten aan het begin van de lus, zoek vervolgens het einde van de cyclus en wijs deze naar nul

Dit werkt omdat ptr1 is k stappen verwijderd van de lus, en ptr2, die wordt vooruitgeschoven door l stappen, ook behoeften k stappen om het einde van de lus te bereiken (n - l = k).

En hier is een eenvoudige, mogelijke implementatie:

openbare klasse CycleRemovalByCountingLoopNodes {privé statische leegte removeCycle (Node loopNodeParam, Node head) {int cycleLength = berekenCycleLength (loopNodeParam); Knooppunt cycleLengthAdvancedIterator = head; Knoop het = hoofd; voor (int i = 0; i <cycleLength; i ++) {cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } while (it.next! = cycleLengthAdvancedIterator.next) {it = it.next; cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } cycleLengthAdvancedIterator.next = null; } privé statische int berekenCycleLength (Node loopNodeParam) {Node loopNode = loopNodeParam; int lengte = 1; while (loopNode.next! = loopNodeParam) {length ++; loopNode = loopNode.next; } retour lengte; }}

Laten we ons vervolgens concentreren op een methode waarbij we zelfs de stap van het berekenen van de luslengte kunnen elimineren.

3.3. Geoptimaliseerde oplossing - zonder de lusknooppunten te tellen

Laten we de afstanden afgelegd door de snelle en langzame wijzers wiskundig vergelijken.

Daarvoor hebben we nog een paar variabelen nodig:

• y = afstand van het punt waar de twee iteratoren elkaar ontmoeten, gezien vanaf het begin van de cyclus
• z = afstand van het punt waar de twee iteratoren elkaar ontmoeten, gezien vanaf het einde van de cyclus (dit is ook gelijk aan l - y)
• m = aantal keren dat de snelle iterator de cyclus voltooide voordat de langzame iterator de cyclus ingaat

Door de andere variabelen hetzelfde te houden zoals gedefinieerd in de vorige sectie, zullen de afstandsvergelijkingen worden gedefinieerd als:

• Afstand afgelegd door langzame wijzer = k (afstand van fiets tot hoofd) + y (ontmoetingspunt binnen cyclus)
• Afstand afgelegd door snelle wijzer = k (afstand van fiets tot hoofd) + m (aantal keren dat de snelle aanwijzer de cyclus voltooide voordat de langzame aanwijzer binnenkomt) * l (cycluslengte) + y (ontmoetingspunt binnen cyclus)

We weten dat de afstand die de snelle aanwijzer aflegt twee keer zo groot is als de langzame aanwijzer, dus:

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

wat resulteert in:

y = m * l - k

Beide zijden aftrekken van l geeft:

l - y = l - m * l + k

of equivalent:

k = (m - 1) * l + z (waarbij l - y z is zoals hierboven gedefinieerd)

Dit leidt tot:

k = (m - 1) Loopt volledige lus + Een extra afstand z

Met andere woorden, als we één iterator bovenaan de lijst en één iterator op het ontmoetingspunt laten staan ​​en ze met dezelfde snelheid verplaatsen, wordt de tweede iterator voltooid m - 1 fietst rond de lus en ontmoet de eerste wijzer aan het begin van de cyclus. Met behulp van dit inzicht kunnen we het algoritme formuleren:

1. Gebruik 'Flyods Cycle-Finding Algorithm' om de lus te detecteren. Als er een lus bestaat, zou dit algoritme eindigen op een punt binnen de lus (noem dit het ontmoetingspunt)
2. Neem twee iteratoren, één bovenaan de lijst (it1) en één op het ontmoetingspunt (it2)
3. Doorkruis beide iteratoren met dezelfde snelheid
4. Aangezien de afstand van de lus tot het hoofd k is (zoals hierboven gedefinieerd), zou de iterator die vanaf het hoofd is gestart, de cyclus bereiken na k stappen
5. In k steps, iterator it2 zou doorkruisen m - 1 cycli van de lus en een extra afstand z. Omdat deze wijzer al op een afstand van was z vanaf het begin van de cyclus, deze extra afstand afleggen z, zou het ook aan het begin van de cyclus brengen
6. Beide iteratoren ontmoeten elkaar aan het begin van de cyclus, vervolgens kunnen we het einde van de cyclus vinden en ernaar verwijzen nul

Dit kan worden geïmplementeerd:

openbare klasse CycleRemovalWithoutCountingLoopNodes {privé statische leegte removeCycle (Node meetingPointParam, Node head) {Node loopNode = meetingPointParam; Knoop het = hoofd; while (loopNode.next! = it.next) {it = it.next; loopNode = loopNode.next; } loopNode.next = null; }}

Dit is de meest geoptimaliseerde aanpak voor het detecteren en verwijderen van cycli uit een gekoppelde lijst.

4. Conclusie

In dit artikel hebben we verschillende algoritmen beschreven voor het detecteren van een cyclus in een lijst. We hebben gekeken naar algoritmen met verschillende rekentijd en geheugenruimte.

Ten slotte hebben we ook drie methoden laten zien om een ​​cyclus te verwijderen, zodra deze is gedetecteerd met behulp van het ‘Flyods Cycle-Finding Algorithm '.

Het volledige codevoorbeeld is beschikbaar op Github.