streamalism.org

1. Uvod

Pojedinačno povezani popis je niz povezanih čvorova koji završavaju s null referenca. Međutim, u nekim scenarijima posljednji čvor može usmjeriti na prethodni čvor - učinkovito stvarajući ciklus.

U većini slučajeva želimo biti u stanju otkriti i biti svjesni tih ciklusa; ovaj će se članak usredotočiti upravo na to - otkrivanje i potencijalno uklanjanje ciklusa.

2. Otkrivanje ciklusa

Istražimo sada nekoliko algoritama za otkrivanje ciklusa na povezanim popisima.

2.1. Brute Force - O (n ^ 2) vremenska složenost

Ovim algoritmom prelazimo popis koristeći dvije ugniježđene petlje. U vanjskoj petlji prelazimo jedan po jedan. U unutarnjoj petlji započinjemo od glave i prelazimo onoliko čvorova koliko je do tada prošla vanjska petlja.

Ako čvor koji posjećuje vanjska petlja dva puta posjeti unutarnja petlja, tada je otkriven ciklus. Suprotno tome, ako vanjska petlja dođe do kraja popisa, to podrazumijeva odsustvo ciklusa:

javni statički boolean detectCycle (glava čvora) {if (head == null) {return false; } Čvor it1 = glava; int nodesTraversedByOuter = 0; while (it1! = null && it1.next! = null) {it1 = it1.next; nodesTraversedByOuter ++; int x = nodesTraversedByOuter; Čvor it2 = glava; int noOfTimesCurrentNodeVisited = 0; while (x> 0) {it2 = it2.naprijed; if (it2 == it1) {noOfTimesCurrentNodeVisited ++; } if (noOfTimesCurrentNodeVisited == 2) {return true; } x--; }} return false; }

Prednost ovog pristupa je u tome što zahtijeva konstantnu količinu memorije. Nedostatak je što je izvedba vrlo spora kada se kao ulaz daju veliki popisi.

2.2. Hashing - O (n) složenost prostora

Ovim algoritmom održavamo skup već posjećenih čvorova. Za svaki čvor provjeravamo postoji li u skupu. Ako nije, tada ga dodajemo skupu. Postojanje čvora u skupu znači da smo čvor već posjetili i dovodi naprijed prisutnost ciklusa na popisu.

Kada naiđemo na čvor koji već postoji u skupu, otkrili bismo početak ciklusa. Nakon što smo to otkrili, lako možemo prekinuti ciklus postavljanjem Sljedeći polje prethodnog čvora do null, kao što je prikazano u nastavku:

javni statički boolean detectCycle (glava čvora) {if (head == null) {return false; } Postavi set = novi HashSet (); Čvor čvor = glava; while (čvor! = null) {if (set.contains (node)) {return true; } set.add (čvor); node = node.next; } return false; }

U ovom smo rješenju posjetili i pohranili svaki čvor jednom. To iznosi složenost vremena O (n) i složenost prostora O (n), što u prosjeku nije optimalno za velike popise.

2.3. Brzi i spori pokazivači

Sljedeći algoritam za pronalaženje ciklusa može se najbolje objasniti koristeći se metaforom.

Uzmite u obzir trkaću stazu na kojoj se utrkuje dvoje ljudi. S obzirom na to da je brzina druge osobe dvostruka brzina prve osobe, druga osoba će obići stazu dvostruko brže od prve i na početku kruga ponovno će se susresti s prvom osobom.

Ovdje se služimo sličnim pristupom ponavljajući popis istovremeno s polaganim i brzim iteratorom (2x brzina). Jednom kad su oba iteratora ušla u petlju, na kraju će se sastati u određenom trenutku.

Stoga, ako se dva iteratora sretnu u bilo kojem trenutku, onda možemo zaključiti da smo naišli na ciklus:

javna statička CycleDetectionResult identifyCycle (glava čvora) {if (head == null) {return new CycleDetectionResult (false, null); } Čvor spor = glava; Čvor brz = glava; dok (brzo! = null && fast.next! = null) {slow = slow.next; brzo = brzo.sljedeće.sljedeće; if (sporo == brzo) {return new CycleDetectionResult (true, fast); }} vrati novi CycleDetectionResult (false, null); }

Gdje Rezultat CycleDetectionResult je praktična klasa za zadržavanje rezultata: a boolean varijabla koja kaže postoji li ciklus ili ne i ako postoji, onda to također sadrži referencu na mjesto susreta unutar ciklusa:

javna klasa CycleDetectionResult {boolean cycleExists; Čvor čvor; }

Ova je metoda poznata i kao „Algoritam kornjače i zeca“ ili „Flyodsov algoritam za pronalaženje ciklusa“.

3. Uklanjanje ciklusa s popisa

Pogledajmo nekoliko metoda za uklanjanje ciklusa. Sve ove metode pretpostavljaju da je za otkrivanje ciklusa korišten "Flyodsov algoritam za pronalaženje ciklusa" koji se temelji na njemu.

3.1. Sirova snaga

Jednom kad se brzi i spori iteratori sretnu u točki ciklusa, uzimamo još jedan iterator (recimo ptr) i usmjerite je na glavu popisa. Ponavljamo popis s ptr. Na svakom koraku provjeravamo je li ptr je dostupan s mjesta sastanka.

Ovo prestaje kada ptr doseže početak petlje jer je to prva točka kada uđe u petlju i postane dostupna s mjesta sastanka.

Jednom početak petlje (bg), tada je trivijalno pronaći kraj ciklusa (čvor čije sljedeće polje pokazuje na bg). Sljedeći pokazivač ovog krajnjeg čvora tada je postavljen na null za uklanjanje ciklusa:

javna klasa CycleRemovalBruteForce {private static void removeCycle (Node loopNodeParam, Node head) {Node it = head; while (it! = null) {if (isNodeReachableFromLoopNode (it, loopNodeParam)) {Node loopStart = it; findEndNodeAndBreakCycle (loopStart); pauza; } it = it.naprijed; }} privatni statički logički isNodeReachableFromLoopNode (Node it, Node loopNodeParam) {Node loopNode = loopNodeParam; do {if (it == loopNode) {return true; } loopNode = loopNode.next; } while (loopNode.next! = loopNodeParam); return false; } privatna statička praznina findEndNodeAndBreakCycle (Node loopStartParam) {Node loopStart = loopStartParam; while (loopStart.next! = loopStartParam) {loopStart = loopStart.next; } loopStart.next = null; }}

Nažalost, ovaj algoritam također ima lošu izvedbu u slučaju velikih popisa i velikih ciklusa, jer moramo ciklus prelaziti više puta.

3.2. Optimizirano rješenje - brojanje petlji

Prvo definirajmo nekoliko varijabli:

• n = veličina popisa
• k = udaljenost od glave popisa do početka ciklusa
• l = veličina ciklusa

Imamo sljedeći odnos između ovih varijabli:

k + l = n

Ovaj odnos koristimo u ovom pristupu. Točnije, kada je iterator koji započinje od početka popisa već putovao l čvorovi, onda mora putovati k više čvorova za postizanje kraja popisa.

Evo opisa algoritma:

1. Kad se susretnu brzi i spori iteratori, pronađite duljinu ciklusa. To se može postići zadržavanjem jednog od iteratora na mjestu dok se nastavlja s drugim iteratorom (ponavljanje normalnom brzinom, jedan po jedan) dok ne dosegne prvi pokazivač, zadržavajući broj posjećenih čvorova. Ovo se računa kao l
2. Uzmite dva iteratora (ptr1 i ptr2) na početku popisa. Premjesti jedan od iteratora (ptr2) l stepenice
3. Sada ponavljajte oba iteratora dok se ne sretnu na početku petlje, a zatim pronađite kraj ciklusa i usmjerite ga na null

To djeluje jer ptr1 je k korak od petlje i ptr2, koji je napredan od l korake, također treba k koraci do kraja petlje (n - l = k).

I evo jednostavne, potencijalne implementacije:

javna klasa CycleRemovalByCountingLoopNodes {privatna statička praznina removeCycle (čvor loopNodeParam, glava čvora) {int cycleLength = izračunajCycleLength (loopNodeParam); Čvor cycleLengthAdvancedIterator = glava; Čvor to = glava; for (int i = 0; i <cycleLength; i ++) {cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } while (it.next! = cycleLengthAdvancedIterator.next) {it = it.next; cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } cycleLengthAdvancedIterator.next = null; } privatni statički int calcuCycleLength (čvor loopNodeParam) {čvor loopNode = loopNodeParam; dužina int = 1; while (loopNode.next! = loopNodeParam) {length ++; loopNode = loopNode.next; } dužina vraćanja; }}

Dalje, usredotočimo se na metodu u kojoj čak možemo eliminirati korak izračunavanja duljine petlje.

3.3. Optimizirano rješenje - bez brojanja petlji

Usporedimo udaljenosti koje su prešli brzi i polagani pokazivači matematički.

Za to nam treba još nekoliko varijabli:

• g = udaljenost točke na kojoj se dva iteratora susreću, gledano s početka ciklusa
• z = udaljenost točke na kojoj se dva iteratora susreću, gledano s kraja ciklusa (to je također jednako l - g)
• m = koliko je puta brzi iterator završio ciklus prije nego što polagani iterator uđe u ciklus

Zadržavajući ostale varijable kao što je definirano u prethodnom odjeljku, jednadžbe udaljenosti definirat će se kao:

• Udaljenost prijeđena sporim pokazivačem = k (udaljenost ciklusa od glave) + g (mjesto susreta unutar ciklusa)
• Udaljenost pređena brzim pokazivačem = k (udaljenost ciklusa od glave) + m (broj puta brzi pokazivač je završio ciklus prije nego što uđe spor pokazivač) * l (duljina ciklusa) + g (mjesto susreta unutar ciklusa)

Znamo da je udaljenost pređena brzim pokazivačem dvostruko veća od one sporoga, dakle:

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

koja procjenjuje na:

y = m * l - k

Oduzimanje obje strane od l daje:

l - y = l - m * l + k

ili ekvivalentno:

k = (m - 1) * l + z (gdje je l - y z, kako je gore definirano)

Ovo vodi do:

k = (m - 1) Pune petlje + dodatna udaljenost z

Drugim riječima, ako jedan iterator zadržimo na čelu popisa i jedan iterator na mjestu sastanka i pomaknemo ih istom brzinom, tada će drugi iterator završiti m - 1 kruži oko petlje i susreće prvi pokazivač na početku ciklusa. Koristeći ovaj uvid možemo formulirati algoritam:

1. Upotrijebite "Flyodsov algoritam za pronalaženje ciklusa" da biste otkrili petlju. Ako petlja postoji, ovaj algoritam bi završio u točki unutar petlje (nazovite to točkom sastanka)
2. Uzmite dva iteratora, jedan na čelu popisa (it1) i jedan na mjestu sastanka (it2)
3. Pređite oba iteratora istom brzinom
4. Budući da je udaljenost petlje od glave k (kako je gore definirano), iterator pokrenut od glave dosegao bi ciklus nakon k stepenice
5. U k koraci, iterator it2 bi prešao m - 1 ciklusa petlje i dodatna udaljenost z. Budući da je ovaj pokazivač već bio na udaljenosti od z od početka ciklusa, prelazeći ovu dodatnu udaljenost z, donijelo bi ga i na početku ciklusa
6. Oba se iteratora susreću na početku ciklusa, nakon čega možemo pronaći kraj ciklusa i usmjeriti ga null

To se može provesti:

javna klasa CycleRemovalWithoutCountingLoopNodes {privatna statička praznina removeCycle (čvor meetingPointParam, glava čvora) {Node loopNode = meetingPointParam; Čvor to = glava; while (loopNode.next! = it.next) {it = it.next; loopNode = loopNode.next; } loopNode.next = null; }}

Ovo je najoptimiziraniji pristup otkrivanju i uklanjanju ciklusa s povezanog popisa.

4. Zaključak

U ovom smo članku opisali razne algoritme za otkrivanje ciklusa na popisu. Istražili smo algoritme s različitim računalnim vremenom i zahtjevima za memorijskim prostorom.

Konačno, pokazali smo i tri metode za uklanjanje ciklusa, nakon što se otkrije pomoću "Flyods algoritma za pronalaženje ciklusa".

Cjelovit primjer koda dostupan je na Githubu.