streamalism.org

1. Úvod

Samostatne prepojený zoznam je postupnosť spojených uzlov končiacich sa nulový odkaz. V niektorých scenároch však posledný uzol môže smerovať na predchádzajúci uzol - čo efektívne vytvorí cyklus.

Vo väčšine prípadov chceme byť schopní tieto cykly zistiť a byť si vedomí; tento článok sa zameria presne na to - detekciu a potenciálne odstránenie cyklov.

2. Detekcia cyklu

Poďme teraz preskúmať niekoľko algoritmov na zisťovanie cyklov v prepojených zoznamoch.

2.1. Brute Force - O (n ^ 2) časová zložitosť

Pomocou tohto algoritmu prechádzame zoznam pomocou dvoch vnorených slučiek. Vo vonkajšej slučke prechádzame jeden po druhom. Vo vnútornej slučke začíname od hlavy a prechádzame toľko uzlov, koľko do tej doby prešlo vonkajšou slučkou.

Ak uzol, ktorý navštívi vonkajšia slučka, navštívi vnútorná slučka dvakrát, potom bol zistený cyklus. Naopak, ak vonkajšia slučka dosiahne koniec zoznamu, znamená to absenciu cyklov:

public static boolean detectCycle (Node head) {if (head == null) {return false; } Uzol it1 = hlava; int nodesTraversedByOuter = 0; while (it1! = null && it1.next! = null) {it1 = it1.next; nodesTraversedByOuter ++; int x = nodesTraversedByOuter; Uzol it2 = hlava; int noOfTimesCurrentNodeVisited = 0; while (x> 0) {it2 = it2.next; if (it2 == it1) {noOfTimesCurrentNodeVisited ++; } if (noOfTimesCurrentNodeVisited == 2) {return true; } X--; }} return false; }

Výhodou tohto prístupu je, že vyžaduje neustále množstvo pamäte. Nevýhodou je, že výkon je veľmi pomalý, ak sa ako vstup poskytujú veľké zoznamy.

2.2. Hashing - O (n) vesmírna zložitosť

Pomocou tohto algoritmu udržiavame množinu už navštívených uzlov. Pre každý uzol skontrolujeme, či v množine existuje. Ak nie, potom ho pridáme do súpravy. Existencia uzla v množine znamená, že sme uzol už navštívili a sprostredkováva tak prítomnosť cyklu v zozname.

Keď narazíme na uzol, ktorý už v množine existuje, objavili by sme začiatok cyklu. Keď to zistíme, môžeme ľahko prelomiť cyklus nastavením hodnoty Ďalšie pole predchádzajúceho uzla do nulový, ako je uvedené nižšie:

public static boolean detectCycle (Node head) {if (head == null) {return false; } Nastav set = new HashSet (); Uzol uzla = hlava; while (node! = null) {if (set.contains (node)) {return true; } set.add (uzol); uzol = node.next; } return false; }

V tomto riešení sme každý uzol navštívili a uložili jedenkrát. To predstavuje O (n) časovú zložitosť a O (n) priestorovú zložitosť, ktorá v priemere nie je optimálna pre veľké zoznamy.

2.3. Rýchle a pomalé ukazovatele

Najlepšie je možné vysvetliť nasledujúci algoritmus na vyhľadanie cyklov pomocou metafory.

Zvážte závodnú dráhu, na ktorej pretekajú dvaja ľudia. Vzhľadom na to, že rýchlosť druhej osoby je dvojnásobná oproti rýchlosti prvej osoby, druhá osoba obíde trať dvakrát rýchlejšie ako prvá a na začiatku kola sa s prvou osobou stretne znova.

Tu používame podobný prístup iteráciou zoznamu súčasne s pomalým a rýchlym iterátorom (2x rýchlosť). Keď obaja iterátori vstúpia do slučky, nakoniec sa stretnú.

Ak sa teda obaja iterátory kedykoľvek stretnú, môžeme dospieť k záveru, že sme narazili na cyklus:

public static CycleDetectionResult detectCycle (Node head) {if (head == null) {return new CycleDetectionResult (false, null); } Uzol pomalý = hlava; Uzol rýchlo = hlava; while (fast! = null && fast.next! = null) {slow = slow.next; fast = fast.next.next; if (slow == fast) {return new CycleDetectionResult (true, fast); }} vrátiť nový CycleDetectionResult (false, null); }

Kde CycleDetectionResult je trieda pohodlia na udržanie výsledku: a boolovský premenná, ktorá hovorí, či cyklus existuje alebo nie, a ak existuje, potom obsahuje aj odkaz na miesto stretnutia vo vnútri cyklu:

verejná trieda CycleDetectionResult {boolean cycleExists; Uzol uzla; }

Táto metóda je tiež známa ako „Algoritmus korytnačky a zajaca“ alebo „Algoritmus hľadania cyklov Flyods“.

3. Odstránenie cyklov zo zoznamu

Pozrime sa na niekoľko metód odstraňovania cyklov. Všetky tieto metódy predpokladajú, že na detekciu cyklu bol použitý algoritmus „Flyods Cycle-Finding Algorithm“, ktorý na ňom nadväzuje.

3.1. Hrubou silou

Akonáhle sa rýchle a pomalé iterátory stretnú v určitom bode cyklu, vezmeme ešte jeden iterátor (povedzme ptr) a nasmerujte ho na čelo zoznamu. Zoznam začneme iterovať pomocou ptr. V každom kroku kontrolujeme, či ptr je dosiahnuteľné z miesta stretnutia.

Týmto sa končí, keď ptr dosiahne začiatok slučky, pretože to je prvý bod, keď vstúpi do slučky a stane sa dosiahnuteľným od bodu stretnutia.

Akonáhle je začiatok slučky (bg), potom je triviálne nájsť koniec cyklu (uzol, na ktorý ďalšie pole ukazuje.) bg). Nasledujúci ukazovateľ tohto koncového uzla sa potom nastaví na nulový na odstránenie cyklu:

verejná trieda CycleRemovalBruteForce {private static void removeCycle (Node loopNodeParam, Node head) {Node it = head; while (it! = null) {if (isNodeReachableFromLoopNode (it, loopNodeParam)) {Node loopStart = it; findEndNodeAndBreakCycle (loopStart); prestávka; } 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); návrat nepravdivý; } private static void findEndNodeAndBreakCycle (Node loopStartParam) {Node loopStart = loopStartParam; while (loopStart.next! = loopStartParam) {loopStart = loopStart.next; } loopStart.next = null; }}

Bohužiaľ, tento algoritmus tiež nefunguje dobre v prípade veľkých zoznamov a veľkých cyklov, pretože musíme cyklom prechádzať viackrát.

3.2. Optimalizované riešenie - počítanie uzlov slučky

Najprv definujme niekoľko premenných:

• n = veľkosť zoznamu
• k = vzdialenosť od začiatku zoznamu po začiatok cyklu
• l = veľkosť cyklu

Medzi týmito premennými máme nasledujúci vzťah:

k + l = n

Tento vzťah využívame v tomto prístupe. Konkrétnejšie, keď iterátor, ktorý začína od začiatku zoznamu, už cestoval l uzly, potom to musí cestovať k viac uzlov, aby ste sa dostali na koniec zoznamu.

Tu je prehľad algoritmu:

1. Keď sa rýchlo a pomaly iterátory stretnú, nájdite dĺžku cyklu. To je možné dosiahnuť tak, že jeden z iterátorov zostane na svojom mieste a druhý iterátor bude pokračovať (iterácia normálnou rýchlosťou jeden po druhom), kým nedosiahne prvý ukazovateľ, čím sa zachová počet navštívených uzlov. Toto sa počíta ako l
2. Vezmite dva iterátory (ptr1 a ptr2) na začiatku zoznamu. Presuňte jeden z iterátorov (ptr2) l krokov
3. Teraz iterujte oba iterátory, až kým sa nestretnú na začiatku slučky, následne nájdite koniec cyklu a nasmerujte ho na nulový

Toto funguje, pretože ptr1 je k kroky od slučky a ptr2, ktorý je rozšírený o l kroky, tiež potreby k kroky na dosiahnutie konca slučky (n - l = k).

A tu je jednoduchá potenciálna implementácia:

verejná trieda CycleRemovalByCountingLoopNodes {private static void removeCycle (Node loopNodeParam, Node head) {int cycleLength = vypočítaťCycleLength (loopNodeParam); Uzol cycleLengthAdvancedIterator = hlava; Uzol to = hlava; pre (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 CalcCycleLength (Node loopNodeParam) {Node loopNode = loopNodeParam; int dĺžka = 1; while (loopNode.next! = loopNodeParam) {dĺžka ++; loopNode = loopNode.next; } dĺžka návratu; }}

Ďalej sa zameriame na metódu, pri ktorej môžeme dokonca vylúčiť krok výpočtu dĺžky slučky.

3.3. Optimalizované riešenie - bez počítania uzlov slučky

Poďme si matematicky porovnať vzdialenosti, ktoré urazili rýchle a pomalé ukazovatele.

Na to potrebujeme ešte niekoľko premenných:

• r = vzdialenosť bodu, kde sa oba iterátory stretávajú, ako je to viditeľné od začiatku cyklu
• z = vzdialenosť bodu, kde sa dva iterátory stretávajú, ako je to viditeľné od konca cyklu (to sa tiež rovná l - r)
• m = koľkokrát rýchly iterátor dokončil cyklus predtým, ako pomalý iterátor vstúpi do cyklu

Pri zachovaní ostatných premenných rovnakých, ako sú definované v predchádzajúcej časti, budú diaľkové rovnice definované ako:

• Vzdialenosť, ktorú prešiel pomalý ukazovateľ k (vzdialenosť cyklu od hlavy) + r (miesto stretnutia vo vnútri cyklu)
• Vzdialenosť, ktorú prešiel rýchly ukazovateľ k (vzdialenosť cyklu od hlavy) + m (žiadny krát rýchly ukazovateľ nedokončil cyklus predtým, ako vstúpi pomalý ukazovateľ) * l (dĺžka cyklu) + r (miesto stretnutia vo vnútri cyklu)

Vieme, že vzdialenosť, ktorú prešiel rýchly ukazovateľ, je dvakrát väčšia ako vzdialenosť pomalého ukazovateľa, a teda:

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

ktorý sa hodnotí na:

y = m * l - k

Odčítaním oboch strán od l dáva:

l - y = l - m * l + k

alebo ekvivalentne:

k = (m - 1) * l + z (kde l - y je z, ako je definované vyššie)

To vedie k:

k = (m - 1) Plná slučka beží + Dodatočná vzdialenosť z

Inými slovami, ak ponecháme jeden iterátor v čele zoznamu a jeden iterátor v mieste stretnutia a presunieme ich rovnakou rýchlosťou, druhý iterátor dokončí m - 1 cykly okolo slučky a na začiatku cyklu sa stretávajú s prvým ukazovateľom. Pomocou tohto prehľadu môžeme formulovať algoritmus:

1. Na detekciu slučky použite algoritmus „Flyods Cycle-Finding Algorithm“. Ak existuje slučka, tento algoritmus by sa skončil v bode vo vnútri slučky (hovorme tomu miesto stretnutia)
2. Vezmite dva iterátory, jeden na začiatku zoznamu (it1) a jeden v mieste stretnutia (it2)
3. Prejdite obidva iterátory rovnakou rýchlosťou
4. Pretože vzdialenosť slučky od hlavy je k (ako je definované vyššie), iterátor začatý od hlavy by dosiahol cyklus po k krokov
5. V k kroky, iterátor it2 by traverzoval m - 1 cykly slučky a vzdialenosť navyše z. Pretože tento ukazovateľ bol už na diaľku z od začiatku cyklu, prejdením tejto extra vzdialenosti z, prinesie to aj na začiatku cyklu
6. Oba iterátory sa stretávajú na začiatku cyklu, následne nájdeme koniec cyklu a ukážeme na neho nulový

Toto je možné implementovať:

public class CycleRemovalWithoutCountingLoopNodes {private static void removeCycle (Node meetingPointParam, Node head) {Node loopNode = meetingPointParam; Uzol to = hlava; while (loopNode.next! = it.next) {it = it.next; loopNode = loopNode.next; } loopNode.next = null; }}

Toto je najoptimálnejší prístup na detekciu a odstránenie cyklov z prepojeného zoznamu.

4. Záver

V tomto článku sme opísali rôzne algoritmy na detekciu cyklu v zozname. Pozreli sme sa na algoritmy s rôznymi požiadavkami na výpočtový čas a pamäťový priestor.

Nakoniec sme tiež ukázali tri metódy na odstránenie cyklu, akonáhle je detekovaný pomocou algoritmu „Flyods Cycle-Finding Algorithm“.

Celý príklad kódu je k dispozícii na stránkach Github.