streamalism.org

1. Introduksjon

En enkelt koblet liste er en sekvens av tilkoblede noder som slutter med a null henvisning. Imidlertid, i noen scenarier, kan den siste noden peke på en tidligere node - effektivt skape en syklus.

I de fleste tilfeller ønsker vi å kunne oppdage og være klar over disse syklusene; denne artikkelen vil fokusere på akkurat det - oppdage og potensielt fjerne sykluser.

2. Oppdage en syklus

La oss nå utforske et par algoritmer for å oppdage sykluser i koblede lister.

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

Med denne algoritmen krysser vi listen ved hjelp av to nestede løkker. I den ytre sløyfen krysser vi en etter en. I den indre sløyfen starter vi fra hodet og krysser så mange noder som krysses av ytre sløyfe på den tiden.

Hvis en node som besøkes av den ytre sløyfen besøkes to ganger av den indre sløyfen, har en syklus blitt oppdaget. Omvendt, hvis den ytre sløyfen når slutten av listen, innebærer dette fravær av sykluser:

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

Fordelen med denne tilnærmingen er at den krever en konstant mengde minne. Ulempen er at ytelsen er veldig treg når store lister blir gitt som innspill.

2.2. Hashing - O (n) Romkompleksitet

Med denne algoritmen opprettholder vi et sett med allerede besøkte noder. For hver node sjekker vi om den finnes i settet. Hvis ikke, så legger vi det til settet. Eksistensen av en node i settet betyr at vi allerede har besøkt noden og fremmer tilstedeværelsen av en syklus i listen.

Når vi møter en node som allerede finnes i settet, ville vi ha oppdaget begynnelsen av syklusen. Etter å ha oppdaget dette, kan vi enkelt bryte syklusen ved å stille inn neste feltet til forrige node til null, som vist nedenfor:

public static boolean detectCycle (Node head) {if (head == null) {return false; } Sett sett = nytt HashSet (); Node node = hode; mens (node! = null) {if (set.contains (node)) {return true; } set.add (node); node = node.next; } returner falsk; }

I denne løsningen besøkte og lagret vi hver node én gang. Dette utgjør O (n) tidskompleksitet og O (n) romkompleksitet, som i gjennomsnitt ikke er optimal for store lister.

2.3. Raske og langsomme pekere

Følgende algoritme for å finne sykluser kan best forklares ved hjelp av en metafor.

Vurder et løpebane der to personer kjører. Gitt at hastigheten til den andre personen er dobbelt så stor som den første personen, vil den andre personen gå rundt banen to ganger så raskt som den første og møte den første personen igjen i begynnelsen av runden.

Her bruker vi en lignende tilnærming ved å iterere gjennom listen samtidig med en langsom iterator og en rask iterator (2x hastighet). Når begge iteratorene har gått inn i en løkke, vil de til slutt møtes på et tidspunkt.

Derfor, hvis de to iteratorene møtes når som helst, så kan vi konkludere med at vi har snublet over en syklus:

offentlig statisk CycleDetectionResult detectCycle (Node head) {if (head == null) {return new CycleDetectionResult (false, null); } Node sakte = hode; Node raskt = hode; mens (fast! = null && fast.next! = null) {slow = slow.next; rask = rask.neste.neste; if (slow == fast) {return new CycleDetectionResult (true, fast); }} returner nye CycleDetectionResult (false, null); }

Hvor CycleDetectionResult er en praktisk klasse for å holde resultatet: a boolsk variabel som sier om syklus eksisterer eller ikke, og hvis den eksisterer, inneholder denne også en referanse til møtepunktet inne i syklusen:

offentlig klasse CycleDetectionResult {boolean cycleExists; Node node; }

Denne metoden er også kjent som 'The Tortoise and The Hare Algorithm' eller 'Flyods Cycle-Finding Algorithm'.

3. Fjerning av sykluser fra en liste

La oss ta en titt på noen få metoder for å fjerne sykluser. Alle disse metodene forutsetter at 'Flyods Cycle-Finding Algorithm' ble brukt til syklusdeteksjon og bygget på toppen av den.

3.1. Ren styrke

Når de raske og langsomme iteratorene møtes på et tidspunkt i syklusen, tar vi en iterator til (si ptr) og pek den mot hodet på listen. Vi begynner å itere listen med ptr. Ved hvert trinn sjekker vi om ptr er tilgjengelig fra møtepunktet.

Dette avsluttes når ptr når begynnelsen av sløyfen fordi det er det første punktet når den kommer inn i sløyfen og blir tilgjengelig fra møtepunktet.

Når begynnelsen av løkken (bg) blir oppdaget, så er det trivielt å finne slutten av syklusen (node ​​hvis neste felt peker mot bg). Neste peker til denne sluttnoden settes deretter til null for å fjerne syklusen:

public class CycleRemovalBruteForce {private static void removeCycle (Node loopNodeParam, Node head) {Node it = head; mens (it! = null) {if (isNodeReachableFromLoopNode (it, loopNodeParam)) {Node loopStart = it; findEndNodeAndBreakCycle (loopStart); gå i stykker; } it = it.next; }} privat statisk boolsk isNodeReachableFromLoopNode (Node it, Node loopNodeParam) {Node loopNode = loopNodeParam; gjør {if (it == loopNode) {return true; } loopNode = loopNode.next; } mens (loopNode.next! = loopNodeParam); returner falsk; } privat statisk tomrom findEndNodeAndBreakCycle (Node loopStartParam) {Node loopStart = loopStartParam; mens (loopStart.next! = loopStartParam) {loopStart = loopStart.next; } loopStart.next = null; }}

Dessverre fungerer denne algoritmen også dårlig i tilfelle store lister og store sykluser, fordi vi må krysse syklusen flere ganger.

3.2. Optimalisert løsning - Telle løkkekodene

La oss definere noen variabler først:

• n = størrelsen på listen
• k = avstanden fra hodet på listen til starten av syklusen
• l = syklusens størrelse

Vi har følgende forhold mellom disse variablene:

k + l = n

Vi bruker dette forholdet i denne tilnærmingen. Mer spesifikt når en iterator som begynner fra starten av listen, allerede har reist l noder, så må den reise k flere noder for å komme til slutten av listen.

Her er algoritmens disposisjon:

1. Når hurtig og de langsomme iteratorene møtes, finn lengden på syklusen. Dette kan gjøres ved å holde en av iteratorene på plass mens du fortsetter den andre iteratoren (iterering med normal hastighet, en etter en) til den når den første pekeren, og holder antall besøkte noder. Dette teller som l
2. Ta to iteratorer (ptr1 og ptr2) i begynnelsen av listen. Flytt en av iteratoren (ptr2) l trinn
3. Nå itererer begge iteratorene til de møtes i starten av løkken, finn deretter slutten av syklusen og pek den mot null

Dette fungerer fordi ptr1 er k skritt fra løkken, og ptr2, som avanseres av l trinn, også behov k trinn for å nå slutten av løkken (n - l = k).

Og her er en enkel, potensiell implementering:

public class CycleRemovalByCountingLoopNodes {private static void removeCycle (Node loopNodeParam, Node head) {int cycleLength = calcCycleLength (loopNodeParam); Node cycleLengthAdvancedIterator = hode; Node it = hode; for (int i = 0; i <cycleLength; i ++) {cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } mens (it.next! = cycleLengthAdvancedIterator.next) {it = it.next; cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } cycleLengthAdvancedIterator.next = null; } privat statisk int-beregneCycleLength (Node loopNodeParam) {Node loopNode = loopNodeParam; int lengde = 1; mens (loopNode.next! = loopNodeParam) {lengde ++; loopNode = loopNode.next; } returlengde; }}

La oss deretter fokusere på en metode der vi til og med kan eliminere trinnet med å beregne sløyfelengden.

3.3. Optimalisert løsning - uten å telle sløyfenodene

La oss sammenligne avstandene som de raske og langsomme pekerne har matematisk.

For det trenger vi noen flere variabler:

• y = avstand til punktet der de to iteratorene møtes, sett fra begynnelsen av syklusen
• z = avstand til punktet der de to iteratorene møtes, sett fra slutten av syklusen (dette er også lik l - y)
• m = antall ganger den raske iteratoren fullførte syklusen før den langsomme iteratoren går inn i syklusen

Ved å holde de andre variablene like som definert i forrige avsnitt, vil avstandsligningene bli definert som:

• Avstand tilbakelagt med langsom peker = k (avstand fra syklus fra hode) + y (møtepunkt inne i syklus)
• Avstand tilbakelagt med hurtigpekeren = k (avstand fra syklus fra hode) + m (antall ganger har hurtigpekeren fullført syklusen før langsom peker kommer inn) * l (sykluslengde) + y (møtepunkt inne i syklus)

Vi vet at avstanden med den hurtige pekeren er dobbelt så lang som den langsomme pekeren, derav:

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

som evalueres til:

y = m * l - k

Trekker begge sider fra l gir:

l - y = l - m * l + k

eller tilsvarende:

k = (m - 1) * l + z (hvor, l - y er z som definert ovenfor)

Dette leder til:

k = (m - 1) Full løpekjøring + En ekstra avstand z

Med andre ord, hvis vi holder en iterator i spissen av listen og en iterator på møtepunktet, og beveger dem i samme hastighet, vil den andre iteratoren fullføre m - 1 sykler rundt løkken og møter den første pekeren i begynnelsen av syklusen. Ved hjelp av denne innsikten kan vi formulere algoritmen:

1. Bruk ‘Flyods Cycle-Finding Algorithm’ for å oppdage løkken. Hvis det finnes en sløyfe, vil denne algoritmen ende på et punkt inne i sløyfen (kaller dette møtepunktet)
2. Ta to iteratorer, en øverst på listen (it1) og en på møtepunktet (it2)
3. Kryss begge iteratorene i samme hastighet
4. Siden avstanden til sløyfen fra hodet er k (som definert ovenfor), ville iteratoren startet fra hodet nå syklusen etter k trinn
5. I k trinn, iterator it2 ville krysset m - 1 sykluser av sløyfen og en ekstra avstand z. Siden denne pekeren allerede var i en avstand på z fra begynnelsen av syklusen, krysser denne ekstra avstanden z, ville bringe det også i begynnelsen av syklusen
6. Begge iteratorene møtes i begynnelsen av syklusen, deretter kan vi finne slutten av syklusen og peke på den null

Dette kan implementeres:

offentlig klasse CycleRemovalWithoutCountingLoopNodes {private static void removeCycle (Node MeetingPointParam, Node head) {Node loopNode = MeetingPointParam; Node it = hode; mens (loopNode.next! = it.next) {it = it.next; loopNode = loopNode.next; } loopNode.next = null; }}

Dette er den mest optimaliserte tilnærmingen for deteksjon og fjerning av sykluser fra en koblet liste.

4. Konklusjon

I denne artikkelen beskrev vi forskjellige algoritmer for å oppdage en syklus i en liste. Vi så på algoritmer med forskjellige krav til databehandlingstid og minne.

Til slutt viste vi også tre metoder for å fjerne en syklus når den oppdages ved hjelp av 'Flyods Cycle-Finding Algorithm'.

Det fulle kodeeksemplet er tilgjengelig på Github.