streamalism.org

1. Introduktion

En enkelt linket liste er en sekvens af forbundne noder, der slutter med a nul reference. I nogle scenarier kan den sidste node dog pege på en tidligere node - hvilket effektivt skaber en cyklus.

I de fleste tilfælde vil vi være i stand til at opdage og være opmærksomme på disse cyklusser; denne artikel vil fokusere på netop det - detektering og potentielt fjernelse af cyklusser.

2. Registrering af en cyklus

Lad os nu undersøge et par algoritmer til at detektere cyklusser i sammenkædede lister.

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

Med denne algoritme krydser vi listen ved hjælp af to indlejrede sløjfer. I den ydre løkke krydser vi en efter en. I den indre sløjfe starter vi fra hovedet og krydser så mange noder, som den ydre sløjfe krydser på det tidspunkt.

Hvis en node, der besøges af den ydre sløjfe, besøges to gange af den indre sløjfe, er en cyklus blevet detekteret. Omvendt, hvis den ydre sløjfe når slutningen af ​​listen, betyder det, at der ikke findes cyklusser:

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

Fordelen ved denne tilgang er, at den kræver en konstant mængde hukommelse. Ulempen er, at ydeevnen er meget langsom, når store lister leveres som input.

2.2. Hashing - O (n) Rumkompleksitet

Med denne algoritme opretholder vi et sæt allerede besøgte noder. For hver knude kontrollerer vi, om den findes i sættet. Hvis ikke, tilføjer vi det til sættet. Eksistensen af ​​en node i sættet betyder, at vi allerede har besøgt noden og frembringer tilstedeværelsen af ​​en cyklus på listen.

Når vi støder på en knude, der allerede findes i sættet, ville vi have opdaget begyndelsen af ​​cyklussen. Efter at have opdaget dette, kan vi let bryde cyklussen ved at indstille Næste felt for den forrige knude til nulsom vist nedenfor:

public static boolean detectCycle (Node head) {if (head == null) {return false; } Indstil sæt = nyt HashSet (); Node node = hoved; mens (node! = null) {if (set.contains (node)) {return true; } set.add (node); node = node.next; } returner falsk; }

I denne løsning besøgte vi og lagrede hver node én gang. Dette svarer til O (n) tidskompleksitet og O (n) rumkompleksitet, hvilket i gennemsnit ikke er optimal for store lister.

2.3. Hurtige og langsomme pointer

Følgende algoritme til at finde cyklusser kan bedst forklares ved hjælp af en metafor.

Overvej et løbebane, hvor to personer kører. Da hastigheden på den anden person er dobbelt så høj som den første person, vil den anden person gå rundt på banen dobbelt så hurtigt som den første og møde den første person igen i begyndelsen af ​​skødet.

Her bruger vi en lignende tilgang ved at gentage gennem listen samtidigt med en langsom iterator og en hurtig iterator (2x hastighed). Når begge iteratorer er kommet ind i en løkke, mødes de til sidst på et tidspunkt.

Derfor, hvis de to iteratorer mødes på et hvilket som helst tidspunkt, så kan vi konkludere, at vi er faldet over en cyklus:

public static CycleDetectionResult detectCycle (Node head) {if (head == null) {return new CycleDetectionResult (false, null); } Node langsom = hoved; Node hurtig = hoved; mens (fast! = null && fast.next! = null) {slow = slow.next; hurtig = hurtig.næste.næste; hvis (langsom == hurtig) {returner ny CycleDetectionResult (sand, hurtig); }} returner nyt CycleDetectionResult (false, null); }

Hvor CycleDetectionResult er en bekvemmelighedsklasse til at holde resultatet: a boolsk variabel, der siger, om cyklus eksisterer eller ej, og hvis der findes, så indeholder denne også en henvisning til mødestedet inde i cyklussen:

offentlig klasse CycleDetectionResult {boolean cycleExists; Nodeknude; }

Denne metode er også kendt som 'The Tortoise and the Hare Algorithm' eller 'Flyods Cycle-Finding Algorithm'.

3. Fjernelse af cykler fra en liste

Lad os se på et par metoder til fjernelse af cyklusser. Alle disse metoder antager, at 'Flyods Cycle-Finding Algorithm' blev brugt til detektion af cykler og bygget oven på den.

3.1. Råstyrke

Når de hurtige og langsomme iteratorer mødes på et tidspunkt i cyklussen, tager vi endnu en iterator (siger ptr) og peg den mod lederen af ​​listen. Vi begynder at gentage listen med ptr. Ved hvert trin kontrollerer vi, om ptr kan nås fra mødestedet.

Dette slutter når ptr når begyndelsen af ​​sløjfen, fordi det er det første punkt, når det kommer ind i sløjfen og kan nås fra mødestedet.

Når begyndelsen af ​​sløjfen (bg) opdages, så er det trivielt at finde slutningen af ​​cyklussen (knude, hvis næste felt peger på bg). Den næste markør på denne slutknude indstilles derefter til nul for at fjerne cyklussen:

offentlig klasse CycleRemovalBruteForce {privat statisk ugyldig removeCycle (Node loopNodeParam, Nodehoved) {Node it = head; mens (it! = null) {if (isNodeReachableFromLoopNode (it, loopNodeParam)) {Node loopStart = it; findEndNodeAndBreakCycle (loopStart); pause; } det = it.next; }} privat statisk boolsk isNodeReachableFromLoopNode (Node it, Node loopNodeParam) {Node loopNode = loopNodeParam; gør {if (it == loopNode) {returner sand; } loopNode = loopNode.next; } mens (loopNode.next! = loopNodeParam); returner falsk; } privat statisk ugyldig findEndNodeAndBreakCycle (Node loopStartParam) {Node loopStart = loopStartParam; mens (loopStart.next! = loopStartParam) {loopStart = loopStart.next; } loopStart.next = null; }}

Desværre fungerer denne algoritme også dårligt i tilfælde af store lister og store cyklusser, fordi vi skal krydse cyklen flere gange.

3.2. Optimeret løsning - Optælling af sløjfeknuderne

Lad os først definere et par variabler:

• n = størrelsen på listen
• k = afstanden fra lederen af ​​listen til starten af ​​cyklussen
• l = cyklusens størrelse

Vi har følgende forhold mellem disse variabler:

k + l = n

Vi bruger dette forhold i denne tilgang. Mere specifikt, når en iterator, der starter fra starten af ​​listen, allerede har rejst l noder, så skal den rejse k flere noder for at nå slutningen af ​​listen.

Her er algoritmens skitse:

1. Når hurtigt og de langsomme iteratorer mødes, skal du finde længden af ​​cyklussen. Dette kan gøres ved at holde en af ​​iteratorerne på plads, mens du fortsætter den anden iterator (iterering ved normal hastighed, en efter en), indtil den når den første markør og holder antallet af besøgte noder. Dette tæller som l
2. Tag to iteratorer (ptr1 og ptr2) i begyndelsen af ​​listen. Flyt en af ​​iteratoren (ptr2) l trin
3. Nu gentager begge iteratorerne, indtil de mødes i starten af ​​sløjfen, find derefter slutningen af ​​cyklussen og peg den mod nul

Dette fungerer fordi ptr1 er k skridt væk fra løkken, og ptr2, som er avanceret af l trin, også behov k trin for at nå slutningen af ​​sløjfen (n - l = k).

Og her er en simpel, potentiel implementering:

public class CycleRemovalByCountingLoopNodes {private static void removeCycle (Node loopNodeParam, Node head) {int cycleLength = calcCycleLength (loopNodeParam); Node cycleLengthAdvancedIterator = hoved; Node det = hoved; 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 længde = 1; mens (loopNode.next! = loopNodeParam) {længde ++; loopNode = loopNode.next; } returlængde; }}

Lad os derefter fokusere på en metode, hvor vi endda kan eliminere trinnet med at beregne sløjfelængden.

3.3. Optimeret løsning - uden at tælle løkkeknuderne

Lad os sammenligne de afstande, som de hurtige og langsomme pegere har tilbagelagt matematisk.

Til det har vi brug for et par flere variabler:

• y = afstanden til det punkt, hvor de to iteratorer mødes, set fra begyndelsen af ​​cyklussen
• z = afstanden til det punkt, hvor de to iteratorer mødes, set fra slutningen af ​​cyklussen (dette er også lig med l - y)
• m = antal gange den hurtige iterator afsluttede cyklussen, før den langsomme iterator går ind i cyklussen

Ved at holde de andre variabler ens som defineret i det foregående afsnit, defineres afstandsligningerne som:

• Afstand tilbagelagt med langsom markør = k (cyklusafstand fra hoved) + y (mødested inde i cyklus)
• Afstand tilbagelagt med hurtig markør = k (cyklusafstand fra hoved) + m (antal gange hurtig markør afsluttet cyklussen inden langsom markør kommer ind) * l (cykluslængde) + y (mødested inde i cyklus)

Vi ved, at afstanden med den hurtige markør er dobbelt så lang som den langsomme markør, derfor:

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

der evalueres til:

y = m * l - k

Trækker begge sider fra l giver:

l - y = l - m * l + k

eller tilsvarende:

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

Dette fører til:

k = (m - 1) Fuld løbskørsel + En ekstra afstand z

Med andre ord, hvis vi holder en iterator i spidsen for listen og en iterator på mødestedet og bevæger dem i samme hastighed, så vil den anden iterator fuldføre m - 1 cykler rundt om løkken og møder den første markør i begyndelsen af ​​cyklussen. Ved hjælp af denne indsigt kan vi formulere algoritmen:

1. Brug 'Flyods Cycle-Finding Algorithm' til at opdage sløjfen. Hvis der findes sløjfe, ville denne algoritme slutte ved et punkt inde i sløjfen (kald dette mødestedet)
2. Tag to iteratorer, en øverst på listen (it1) og en på mødestedet (it2)
3. Kryds begge iteratorer i samme hastighed
4. Da sløjfens afstand fra hovedet er k (som defineret ovenfor), ville iteratoren startet fra hovedet nå cyklen efter k trin
5. I k trin, iterator it2 ville krydse m - 1 sløjferne og en ekstra afstand z. Da denne markør allerede var i en afstand af z fra begyndelsen af ​​cyklussen, krydser denne ekstra afstand z, ville bringe det også i begyndelsen af ​​cyklussen
6. Begge iteratorerne mødes i begyndelsen af ​​cyklussen, efterfølgende kan vi finde slutningen af ​​cyklussen og pege på den nul

Dette kan implementeres:

public class CycleRemovalWithoutCountingLoopNodes {private static void removeCycle (Node MeetingPointParam, Nodehoved) {Node loopNode = MeetingPointParam; Node det = hoved; mens (loopNode.next! = it.next) {it = it.next; loopNode = loopNode.next; } loopNode.next = null; }}

Dette er den mest optimerede tilgang til detektion og fjernelse af cyklusser fra en sammenkædet liste.

4. Konklusion

I denne artikel beskrev vi forskellige algoritmer til detektering af en cyklus på en liste. Vi kiggede på algoritmer med forskellige krav til computertid og hukommelsesplads.

Endelig viste vi også tre metoder til at fjerne en cyklus, når den først er registreret ved hjælp af 'Flyods Cycle-Finding Algorithm'.

Det fulde kodeeksempel er tilgængeligt på Github.