streamalism.org

1. Prehľad

V tomto výučbe vysvetlíme, ako nájsť prostredný prvok prepojeného zoznamu v prostredí Java.

Hlavné problémy si predstavíme v ďalších častiach a ukážeme si rôzne prístupy k ich riešeniu.

2. Sledovanie veľkosti

Tento problém možno ľahko vyriešiť iba pomocou sledovanie veľkosti, keď do zoznamu pridávame nové prvky. Ak poznáme veľkosť, vieme aj to, kde je stredný prvok, takže riešenie je malicherné.

Pozrime sa na príklad použitia implementácie Java a LinkedList:

public static Voliteľné findMiddleElementLinkedList (LinkedList linkedList) {if (linkedList == null || linkedList.isEmpty ()) {return Optional.empty (); } návrat Optional.of (linkedList.get ((linkedList.size () - 1) / 2)); }

Ak skontrolujeme interný kód LinkedList triedy, môžeme vidieť, že v tomto príklade iba prechádzame zoznamom, kým sa nedostaneme k prostrednému prvku:

Uzol uzla (int index) {if (index> 1)) {Uzol x = prvý; pre (int i = 0; i <index; i ++) {x = x.next; } návrat x; } else {Uzol x = posledný; pre (int i = veľkosť - 1; i> index; i--) {x = x.prev; } návrat x; }}

3. Nájdenie stredu bez znalosti veľkosti

Je veľmi bežné, že sa stretávame s problémami kdekoľvek máme iba hlavný uzol prepojeného zoznamu, a musíme nájsť stredný prvok. V takom prípade nevieme veľkosť zoznamu, čo sťažuje vyriešenie tohto problému.

V nasledujúcich častiach si ukážeme niekoľko prístupov k riešeniu tohto problému, najskôr je však potrebné vytvoriť triedu, ktorá bude predstavovať uzol zoznamu.

Vytvorme a Uzol triedy, ktorá skladuje String hodnoty:

verejná statická trieda Uzol {súkromný uzol ďalej; súkromné ​​údaje reťazca; // konštruktory / getre / setre public boolean hasNext () {návrat ďalej! = null; } public void setNext (uzol ďalší) {this.next = ďalší; } public String toString () {return this.data; }}

Túto pomocnú metódu použijeme aj v našich testovacích prípadoch na vytvorenie jednotlivo prepojeného zoznamu iba pomocou našich uzlov:

privátny statický uzol createNodesList (int n) {hlava uzla = nový uzol ("1"); Prúd uzla = hlava; for (int i = 2; i <= n; i ++) {Node newNode = new Node (String.valueOf (i)); current.setNext (newNode); current = newNode; } vratna hlavica; }

3.1. Najprv nájdite veľkosť

Najjednoduchším prístupom k riešeniu tohto problému je najprv vyhľadať veľkosť zoznamu a potom nasledovať rovnaký prístup, aký sme použili predtým - iterovať až do stredného prvku.

Pozrime sa na toto riešenie v akcii:

public static Voliteľné findMiddleElementFromHead (hlava uzla) {if (head == null) {návrat Optional.empty (); } // vypočítať veľkosť zoznamu Uzol current = head; int veľkosť = 1; while (current.hasNext ()) {current = current.next (); veľkosť ++; } // iterácia do stredného prvku current = head; pre (int i = 0; i <(veľkosť - 1) / 2; i ++) {current = current.next (); } návrat Optional.of (current.data ()); }

Ako vidíme, tento kód iteruje zoznamom dvakrát. Preto má toto riešenie slabý výkon a neodporúča sa.

3.2. Nájdenie stredného prvku v jednom prechode iteračne

Teraz vylepšíme predchádzajúce riešenie nájdením stredného prvku s iba jednou iteráciou v zozname.

Aby sme to mohli robiť iteratívne, potrebujeme dva ukazovatele, aby sme iterovali zoznamom súčasne. Jeden ukazovateľ postúpi o 2 uzly v každej iterácii a druhý ukazovateľ posunie dopredu iba o jeden uzol na každú iteráciu.

Keď rýchlejší ukazovateľ dosiahne koniec zoznamu, pomalší bude v strede:

public static Voliteľné findMiddleElementFromHead1PassIteratively (hlava uzla) {if (head == null) {return Optional.empty (); } Uzol slowPointer = hlava; Uzol fastPointer = hlava; while (fastPointer.hasNext () && fastPointer.next (). hasNext ()) {fastPointer = fastPointer.next (). next (); slowPointer = slowPointer.next (); } návrat Optional.ofNullable (slowPointer.data ()); }

Toto riešenie môžeme otestovať jednoduchým testom jednotiek pomocou zoznamov s nepárnym aj párnym počtom prvkov:

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

3.3. Nájdenie stredného prvku v jednom prechode rekurzívne

Ďalším spôsobom, ako vyriešiť tento problém v jednom prechode, je použitie rekurzie. Môžeme iterovať až do konca zoznamu, aby sme vedeli veľkosť a pri spätných volaniach len počítame do polovice veľkosti.

Aby sme to dosiahli v Jave, vytvoríme pomocnú triedu, ktorá zachová odkazy na veľkosť zoznamu a stredný prvok počas vykonávania všetkých rekurzívnych volaní:

súkromná statická trieda MiddleAuxRecursion {stredný uzol; int dĺžka = 0; }

Teraz implementujme rekurzívnu metódu:

private static void findMiddleRecursively (Node node, MiddleAuxRecursion middleAux) {if (node ​​== null) {// dosiahol koniec middleAux.length = middleAux.length / 2; návrat; } strednáAux.dĺžka ++; findMiddleRecursively (node.next (), middleAux); if (middleAux.length == 0) {// našiel stredný middleAux.middle = uzol; } strednáAux.dĺžka--; }

A nakoniec vytvorme metódu, ktorá volá rekurzívnu:

public static Voliteľné findMiddleElementFromHead1PassRecursively (Node head) {if (head == null) {return Optional.empty (); } MiddleAuxRecursion middleAux = nový MiddleAuxRecursion (); findMiddleRecursively (head, middleAux); návrat Optional.of (middleAux.middle.data ()); }

Opäť to môžeme testovať rovnakým spôsobom ako predtým:

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

4. Záver

V tomto článku sme predstavili problém hľadania stredného prvku prepojeného zoznamu v prostredí Java a ukázali sme rôzne spôsoby jeho riešenia.

Vychádzali sme z najjednoduchšieho prístupu, kde sme sledovali veľkosť, a potom sme pokračovali v riešeniach hľadania stredného prvku z hlavného uzla zoznamu.

Celý zdrojový kód príkladov je ako vždy k dispozícii na serveri GitHub.