streamalism.org

1. Áttekintés

Ebben az oktatóanyagban elmagyarázzuk, hogyan lehet megtalálni a csatolt lista középső elemét a Java-ban.

A főbb problémákat a következő szakaszokban mutatjuk be, és különböző megközelítéseket mutatunk be azok megoldására.

2. A méret nyomon követése

Ez a probléma egyszerűen megoldható a méret nyomon követése, amikor új elemeket adunk a listához. Ha tudjuk a méretet, akkor azt is tudjuk, hol van a középső elem, így a megoldás triviális.

Lássunk egy példát az a Java implementációjára LinkedList:

public static Opcionális findMiddleElementLinkedList (LinkedList linkedList) {if (linkedList == null || linkedList.isEmpty ()) {return Opcionális.empty (); } return Optional.of (linkedList.get ((linkedList.size () - 1) / 2)); }

Ha ellenőrizzük a LinkedList osztályban láthatjuk, hogy ebben a példában csak haladunk a listán, amíg el nem érjük a középső elemet:

Csomópont csomópont (int index) {if (index> 1)) {Csomópont x = első; for (int i = 0; i <index; i ++) {x = x. következő; } return x; } else {Csomópont x = utolsó; for (int i = méret - 1; i> index; i--) {x = x.prev; } return x; }}

3. A középső megtalálása a méret ismerete nélkül

Nagyon gyakori, hogy hol találkozunk problémákkal csak egy összekapcsolt lista fejcsomópontja van, és meg kell találnunk a középső elemet. Ebben az esetben nem ismerjük a lista méretét, ami megnehezíti a probléma megoldását.

A következő szakaszokban bemutatjuk a probléma megoldásának számos megközelítését, de először létre kell hoznunk egy osztályt, amely a lista csomópontját képviseli.

Hozzunk létre egy Csomópont osztály, amely tárolja Húr értékek:

public static class Node {private Node next; privát karakterlánc-adatok; // constructors / getters / setters public boolean hasNext () {return next! = null; } public void setNext (Node next) {this.next = next; } public String toString () {adja vissza ezeket az adatokat; }}

Ezenkívül ezt a segítő módszert használjuk teszteseteinkben is, hogy csak csomópontjaink segítségével hozzunk létre egy-egy összekapcsolt listát:

privát statikus csomópont createNodesList (int n) {Csomópont = új Csomópont ("1"); Csomópont áram = fej; for (int i = 2; i <= n; i ++) {Csomópont newNode = új Csomópont (String.valOO (i)); current.setNext (newNode); current = newNode; } visszatérő fej; }

3.1. Először a méret megtalálása

A probléma kezelésének legegyszerűbb megközelítése az, hogy először megtalálja a lista méretét, majd ezt követően követi ugyanazt a megközelítést, amelyet korábban használtunk - a középső elemig történő ismétléshez.

Lássuk ezt a megoldást működés közben:

public static Opcionális findMiddleElementFromHead (Node head) {if (head == null) {return Opcionális.empty (); } // kiszámítja a lista méretét Csomópont current = head; int méret = 1; while (current.hasNext ()) {current = current.next (); méret ++; } // iterál a középső elemig current = head; for (int i = 0; i <(méret - 1) / 2; i ++) {current = current.next (); } return Optional.of (current.data ()); }

Ahogy látjuk, ez a kód kétszer ismétli a listát. Ezért ennek a megoldásnak gyenge a teljesítménye, ezért nem ajánlott.

3.2. A középső elem megtalálása egy menetben iteratív módon

Most javítani fogjuk az előző megoldást azzal, hogy megtaláljuk a középső elemet, csak egy iterációval a listán.

Ennek iteratív végrehajtásához két mutatóra van szükségünk a lista egyszerre történő ismétléséhez. Az egyik mutató 2 csomópontot visz előre minden egyes iterációban, a másik mutató pedig csak egy csomópontot visz előre iterációnként.

Amikor a gyorsabb mutató eléri a lista végét, a lassabb mutató a közepén lesz:

public static Opcionális findMiddleElementFromHead1PassIterative (Node head) {if (head == null) {return Opcionális.empty (); } Csomópont slowPointer = fej; Csomópont fastPointer = fej; while (fastPointer.hasNext () && fastPointer.next (). hasNext ()) {fastPointer = fastPointer.next (). next (); slowPointer = slowPointer.next (); } return Optional.ofNullable (slowPointer.data ()); }

Kipróbálhatjuk ezt a megoldást egy egyszerű egységteszt segítségével, páratlan és páros számú elemek listájával:

@Test public void whenFindingMiddleFromHead1PassIterative_thenMiddleFound () {assertEquals ("3", MiddleElementLookup .findMiddleElementFromHead1PassIterative (createNodesList (5)). Get ()); assertEquals ("2", MiddleElementLookup .findMiddleElementFromHead1PassIterative (reateNodesList (4)). get ()); }

3.3. Rekurzív módon a középső elem megtalálása egy menetben

A probléma egy menetben történő megoldásának másik módja a rekurzió használata. Iterálhatunk a lista végéig, hogy megtudjuk a méretet, és a visszahívásokban csak a méret feléig számolunk.

Ehhez a Java-ban létrehozunk egy segédosztályt, amely megőrzi a listaméret és a középső elem referenciáit az összes rekurzív hívás végrehajtása során:

private static class MiddleAuxRecursion {Csomópont közepe; int hossza = 0; }

Most valósítsuk meg a rekurzív módszert:

private static void findMiddleRecursively (Csomópont csomópont, MiddleAuxRecursion middleAux) {if (csomópont == null) {// elérte a végét middleAux.length = middleAux.length / 2; Visszatérés; } middleAux.length ++; findMiddleRecursively (node.next (), middleAux); if (middleAux.length == 0) {// megtalálta a középső middleAux.middle = csomópontot; } middleAux.length--; }

Végül hozzunk létre egy módszert, amely rekurzívnak hívja:

public static Opcionális findMiddleElementFromHead1PassRecursively (Node head) {if (head == null) {return Opcionális.empty (); } MiddleAuxRecursion middleAux = új MiddleAuxRecursion (); findMiddleRecursively (fej, middleAux); return Optional.of (middleAux.middle.data ()); }

Ismét ugyanúgy tesztelhetjük, mint korábban:

@Test public void whenFindingMiddleFromHead1PassRecursively_thenMiddleFound () {assertEquals ("3", MiddleElementLookup .findMiddleElementFromHead1PassRecursively (createNodesList (5)). Get ()); assertEquals ("2", MiddleElementLookup .findMiddleElementFromHead1PassRecursively (createNodesList (4)). get ()); }

4. Következtetés

Ebben a cikkben bemutattuk a összekapcsolt lista középső elemének megkeresésének problémáját a Java-ban, és különböző megoldási módokat mutattunk be.

A legegyszerűbb megközelítésből indultunk, ahol nyomon követtük a méretet, és ezt követően folytattuk a megoldásokat, hogy megtaláljuk a középső elemet a lista fejcsomópontjából.

Mint mindig, a példák teljes forráskódja elérhető a GitHubon.