Tesztelje a kapcsolt listák ciklikusságát

1. Bemutatkozás

Az egyesével összekapcsolt lista az a-val végződő összekapcsolt csomópontok sorozata nulla referencia. Bizonyos esetekben azonban az utolsó csomópont egy korábbi csomópontra mutathat - hatékonyan létrehozva egy ciklust.

A legtöbb esetben azt akarjuk, hogy képesek legyünk észlelni és ismerni ezeket a ciklusokat; ez a cikk pontosan erre fog koncentrálni - a ciklusok felderítésére és potenciálisan eltávolítására.

2. Ciklus észlelése

Fedezzünk fel néhány algoritmust a ciklusok detektálására a kapcsolt listákban.

2.1. Brute Force - O (n ^ 2) Komplex idő

Ezzel az algoritmussal két beágyazott hurok segítségével haladunk át a listán. A külső hurokban egyenként haladunk. A belső hurokban a fejből indulunk, és annyi csomópontot haladunk át, ahányszor a külső hurok áthalad.

Ha egy csomópontot, amelyet a külső hurok látogat meg, a belső hurok kétszer meglátogatja, akkor egy ciklust észleltek. Ezzel szemben, ha a külső hurok eléri a lista végét, ez ciklusok hiányát jelenti:

public static boolean detectCycle (Node head) {if (head == null) {return false; } Csomópont it1 = fej; int csomópontokTraversedByOuter = 0; while (it1! = null && it1.next! = null) {it1 = it1.next; csomópontokTraversedByOuter ++; int x = csomópontokTraversedByOuter; Csomópont it2 = fej; int noOfTimesCurrentNodeVisited = 0; míg (x> 0) {it2 = it2.következő; if (it2 == it1) {noOfTimesCurrentNodeVisited ++; } if (noOfTimesCurrentNodeVisited == 2) {true igaz; } x--; }} return false; }

Ennek a megközelítésnek az az előnye, hogy állandó memóriamennyiséget igényel. Hátránya, hogy a teljesítmény nagyon lassú, ha nagy listákat adunk meg bemenetként.

2.2. Hashing - O (n) Tér komplexitás

Ezzel az algoritmussal fenntartjuk a már meglátogatott csomópontok halmazát. Minden csomópontnál ellenőrizzük, hogy létezik-e a halmazban. Ha nem, akkor hozzáadjuk a készlethez. A csomópont megléte a halmazban azt jelenti, hogy már meglátogattuk a csomópontot, és előrehoztuk egy ciklus jelenlétét a listában.

Amikor egy olyan csomópontra bukkanunk, amely már létezik a készletben, akkor felfedeztük a ciklus kezdetét. Miután felfedeztük ezt, könnyen meg tudjuk szakítani a ciklust a következő mező az előző csomópont nullaaz alábbiak szerint:

public static boolean detectCycle (Node head) {if (head == null) {return false; } Beállítás set = new HashSet (); Csomópont csomópont = fej; while (csomópont! = null) {if (set.contains (csomópont)) {return true; } set.add (csomópont); csomópont = csomópont.következő; } return false; }

Ebben a megoldásban minden csomópontot egyszer meglátogattunk és tároltunk. Ez O (n) idő komplexitást és O (n) tér komplexitást jelent, ami átlagosan nem optimális nagy listák esetén.

2.3. Gyors és lassú mutatók

A ciklusok megtalálásának következő algoritmusa magyarázható meg legjobban metafora segítségével.

Vegyünk egy versenypályát, ahol két ember versenyez. Tekintettel arra, hogy a második személy sebessége duplája az első ember sebességének, a második kétszer olyan gyorsan megy meg a pályán, mint az első, és a kör elején ismét találkozik az elsővel.

Itt hasonló megközelítést alkalmazunk, ha a listán keresztül lassú iterátorral és gyors iterátorral (2x sebesség) egyszerre iterálunk. Miután mindkét iterátor belépett egy ciklusba, végül találkoznak egy ponton.

Ezért, ha a két iterátor találkozik valamikor, akkor arra a következtetésre juthatunk, hogy egy ciklusba botlottunk:

public static CycleDetectionResult DetectCycle (Node head) {if (head == null) {return new CycleDetectionResult (false, null); } Csomópont lassú = fej; Csomópont gyors = fej; while (gyors! = null && fast.next! = null) {slow = slow.next; gyors = gyors.következő.következő; if (lassú == gyors) {return new CycleDetectionResult (true, fast); }} return new CycleDetectionResult (false, null); }

Hol CycleDetectionResult egy kényelmi osztály az eredmény megtartására: a logikai változó, amely megmondja, hogy létezik-e ciklus vagy sem, és ha létezik, akkor ez hivatkozást tartalmaz a cikluson belüli találkozási pontra is:

public class CycleDetectionResult {logikai ciklusExisták; Csomópont csomópont; }

Ez a módszer más néven „A teknős és a nyúl algoritmus” vagy „Flyods cikluskereső algoritmus” néven is ismert.

3. A ciklusok törlése a listáról

Nézzünk meg néhány módszert a ciklusok eltávolítására. Mindezek a módszerek azt feltételezik, hogy a „Flyods Cycle-Finding Algorithm” -et alkalmazták a ciklus detektálására és arra építettek.

3.1. Nyers erő

Miután a gyors és a lassú iterátor találkozik a ciklus egy pontján, még egy iterátort veszünk fel (mondjuk ptr), és mutassa a lista élére. A listát a ptr gombbal kezdjük iterálni. Minden lépésnél ellenőrizzük, hogy ptr a találkozási pontról elérhető.

Ez akkor szűnik meg, amikor ptr eléri a hurok elejét, mert ez az első pont, amikor belép a ciklusba, és elérhetővé válik a találkozási ponttól.

Miután a hurok kezdete (bg), akkor triviális megtalálni a ciklus végét (csomópont, amelynek következő mezője mutat bg). Ezután ennek a végpontnak a következő mutatóját állítja nulla a ciklus eltávolításához:

public class CycleRemovalBruteForce {private static void removeCycle (Node loopNodeParam, Node head) {Node it = fej; while (it! = null) {if (isNodeReachableFromLoopNode (it, loopNodeParam)) {Csomópont loopStart = it; findEndNodeAndBreakCycle (loopStart); szünet; } it = it.next; }} privát statikus logikai isNodeReachableFromLoopNode (Node it, Node loopNodeParam) {Node loopNode = loopNodeParam; do {if (it == loopNode) {return true; } loopNode = loopNode.next; } while (loopNode.next! = loopNodeParam); return false; } private static void findEndNodeAndBreakCycle (Node loopStartParam) {Node loopStart = loopStartParam; while (loopStart.next! = loopStartParam) {loopStart = loopStart.next; } loopStart.next = null; }}

Sajnos ez az algoritmus nagy listák és nagy ciklusok esetén is rosszul teljesít, mert a ciklust többször is meg kell haladnunk.

3.2. Optimalizált megoldás - a hurokcsomópontok számlálása

Először definiáljunk néhány változót:

  • n = a lista mérete
  • k = a távolság a lista elejétől a ciklus kezdetéig
  • l = a ciklus mérete

E változók között a következő kapcsolat áll fenn:

k + l = n

Ezt a kapcsolatot ebben a megközelítésben hasznosítjuk. Pontosabban, amikor a lista elejétől kezdődő iterátor már utazott l csomópontok, akkor utaznia kell k további csomópontok a lista végének eléréséhez.

Itt van az algoritmus vázlata:

  1. Ha a gyors és a lassú iterátor találkozik, keresse meg a ciklus hosszát. Ezt úgy tehetjük meg, hogy az egyik iterátort a helyén tartjuk, miközben a másik iterátort folytatjuk (normál sebességgel iterálva, egyesével), amíg el nem éri az első mutatót, megtartva a meglátogatott csomópontok számát. Ez számít l
  2. Vegyünk két iterátort (ptr1 és ptr2) a lista elején. Mozgassa az egyik iterátort (ptr2) l lépések
  3. Most iterálja mindkét iterátort, amíg össze nem érnek a ciklus elején, majd megtalálja a ciklus végét, és mutasson rá nulla

Ez azért működik, mert ptr1 van k lépésnyire van a huroktól, és ptr2, amelyet előrehaladott l lépéseket, szintén igényeket k lépések a hurok végének eléréséhez (n - l = k).

És itt van egy egyszerű, lehetséges megvalósítás:

public class CycleRemovalByCountingLoopNodes {private static void removeCycle (Node loopNodeParam, Node head) {int ciklushossz = calcCycleLength (loopNodeParam); Csomópont cycleLengthAdvancedIterator = fej; Csomópont it = fej; for (int i = 0; i <ciklushossz; i ++) {ciklusHosszAdvancedIterator = ciklushosszAdvancedIterator.next; } while (it.next! = cycleLengthAdvancedIterator.next) {it = it.next; cycleLengthAdvancedIterator = cycleLengthAdvancedIterator.next; } cycleLengthAdvancedIterator.next = null; } privát statikus int calcCycleLength (Node loopNodeParam) {Node loopNode = loopNodeParam; int hossza = 1; while (loopNode.next! = loopNodeParam) {hossz ++; loopNode = loopNode.next; } visszatérési hossz; }}

Ezután összpontosítsunk egy olyan módszerre, amelyben akár a hurokhossz kiszámításának lépését is kiküszöbölhetjük.

3.3. Optimalizált megoldás - a hurokcsomópontok számlálása nélkül

Hasonlítsuk össze matematikailag a gyors és lassú mutatók által megtett távolságokat.

Ehhez még néhány változóra van szükségünk:

  • y = a két iterátor találkozási pontjának távolsága, a ciklus elejétől nézve
  • z = a két iterátor találkozási pontjának távolsága, a ciklus végétől nézve (ez is megegyezik l - y)
  • m = azok száma, ahányszor a gyors iterátor befejezte a ciklust, mielőtt a lassú iterátor belépne a ciklusba

Ha a többi változó ugyanaz marad, mint ahogy azt az előző szakasz meghatározta, akkor a távolságegyenleteket a következőképpen határozzuk meg:

  • Lassú mutató által megtett távolság = k (a ciklus távolsága a fejtől) + y (találkozási pont a cikluson belül)
  • Gyors mutató által megtett távolság = k (a ciklus távolsága a fejtől) + m (ahányszor a gyors mutató befejezte a ciklust, mielőtt a lassú mutató belépne) * l (ciklus hossza) + y (találkozási pont a cikluson belül)

Tudjuk, hogy a gyors mutató által megtett távolság kétszerese a lassú mutatónak, ezért:

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

amely a következőket értékeli:

y = m * l - k

Kivonva mindkét oldalt l ad:

l - y = l - m * l + k

vagy azzal egyenértékűen:

k = (m - 1) * l + z (ahol, l - y jelentése z, a fentiek szerint definiálva)

Ez ahhoz vezet:

k = (m - 1) Teljes kör fut + Egy további z távolság

Más szavakkal, ha egy iterátort tartunk a lista élén, és egy iterátort a találkozási ponton, és ugyanolyan sebességgel mozgatjuk őket, akkor a második iterátor teljes lesz m - 1 a ciklus körül, és a ciklus elején találkozik az első mutatóval. Ezen betekintés segítségével megfogalmazhatjuk az algoritmust:

  1. A hurok felismeréséhez használja a „Flyods Cycle-Finding Algorithm” alkalmazást. Ha létezik hurok, akkor ez az algoritmus a hurok belsejében egy ponton végződik (hívjuk ezt találkozási pontnak)
  2. Vegyünk két iterátort, egyet a lista élére (it1) és egyet a találkozási ponton (it2)
  3. Keresse meg mindkét iterátort azonos sebességgel
  4. Mivel a hurok feje távolsága k (a fentiek szerint definiálva), a fejről indított iterátor eléri a ciklust k lépések
  5. Ban ben k lépések, iterátor it2 bejárná m - 1 a hurok ciklusai és egy extra távolság z. Mivel ez a mutató már a távolságtól volt z a ciklus elejétől kezdve ezt az extra távolságot haladva z, a ciklus elején is hozná
  6. Mindkét iterátor a ciklus elején találkozik, ezt követően megtalálhatjuk a ciklus végét és ráirányíthatjuk nulla

Ez megvalósítható:

public class CycleRemovalWithoutCountingLoopNodes {private static void removeCycle (Node meetingPointParam, Node head) {Node loopNode = meetingPointParam; Csomópont it = fej; while (loopNode.next! = it.next) {it = it.next; loopNode = loopNode.next; } loopNode.next = null; }}

Ez a legoptimálisabb megközelítés a ciklusok észleléséhez és eltávolításához egy összekapcsolt listáról.

4. Következtetés

Ebben a cikkben különféle algoritmusokat írtunk le egy ciklus detektálására a listában. Különböző számítási idő- és memóriaterületigényű algoritmusokat vizsgáltunk.

Végül három módszert is bemutattunk egy ciklus eltávolítására, amint azt a „Flyods Cycle-Finding Algorithm” segítségével észleltük.

A teljes kód példa elérhető a Github oldalon.