Suchen Sie das mittlere Element einer verknüpften Liste in Java

1. Übersicht

In diesem Tutorial erklären wir, wie Sie das mittlere Element einer verknüpften Liste in Java finden.

In den nächsten Abschnitten werden die Hauptprobleme vorgestellt und verschiedene Lösungsansätze aufgezeigt.

2. Verfolgen Sie die Größe

Dieses Problem kann einfach gelöst werden, indem Sie die Größe verfolgen, wenn Sie der Liste neue Elemente hinzufügen . Wenn wir die Größe kennen, wissen wir auch, wo sich das mittlere Element befindet, sodass die Lösung trivial ist.

Sehen wir uns ein Beispiel mit der Java-Implementierung einer LinkedList an :

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

Wenn wir den internen Code der LinkedList- Klasse überprüfen , können wir sehen, dass wir in diesem Beispiel nur die Liste durchlaufen, bis wir das mittlere Element erreichen:

Node node(int index) { if (index > 1)) { Node x = first; for (int i = 0; i < index; i++) { x = x.next; } return x; } else { Node x = last; for (int i = size - 1; i > index; i--) { x = x.prev; } return x; } }

3. Die Mitte finden, ohne die Größe zu kennen

Es kommt sehr häufig vor, dass wir auf Probleme stoßen, bei denen wir nur den Hauptknoten einer verknüpften Liste haben und das mittlere Element finden müssen. In diesem Fall kennen wir die Größe der Liste nicht, was die Lösung dieses Problems erschwert.

Wir werden in den nächsten Abschnitten verschiedene Ansätze zur Lösung dieses Problems zeigen, aber zuerst müssen wir eine Klasse erstellen, um einen Knoten der Liste darzustellen.

Erstellen wir eine Node- Klasse, in der String- Werte gespeichert werden:

public static class Node { private Node next; private String data; // constructors/getters/setters public boolean hasNext() { return next != null; } public void setNext(Node next) { this.next = next; } public String toString() { return this.data; } }

Außerdem verwenden wir diese Hilfsmethode in unseren Testfällen, um eine einfach verknüpfte Liste nur mit unseren Knoten zu erstellen:

private static Node createNodesList(int n) { Node head = new Node("1"); Node current = head; for (int i = 2; i <= n; i++) { Node newNode = new Node(String.valueOf(i)); current.setNext(newNode); current = newNode; } return head; }

3.1. Zuerst die Größe finden

Der einfachste Ansatz, um dieses Problem zu lösen, besteht darin, zuerst die Größe der Liste zu ermitteln und danach denselben Ansatz zu verwenden, den wir zuvor verwendet haben - bis zum mittleren Element zu iterieren.

Lassen Sie uns diese Lösung in Aktion sehen:

public static Optional findMiddleElementFromHead(Node head) { if (head == null) { return Optional.empty(); } // calculate the size of the list Node current = head; int size = 1; while (current.hasNext()) { current = current.next(); size++; } // iterate till the middle element current = head; for (int i = 0; i < (size - 1) / 2; i++) { current = current.next(); } return Optional.of(current.data()); }

Wie wir sehen können, durchläuft dieser Code die Liste zweimal. Daher weist diese Lösung eine schlechte Leistung auf und wird nicht empfohlen .

3.2. Iterativ das mittlere Element in einem Durchgang finden

Wir werden jetzt die vorherige Lösung verbessern, indem wir das mittlere Element mit nur einer Iteration über der Liste finden.

Um dies iterativ zu tun, benötigen wir zwei Zeiger, um gleichzeitig die Liste zu durchlaufen. Ein Zeiger rückt 2 Knoten in jeder Iteration vor, und der andere Zeiger rückt nur einen Knoten pro Iteration vor .

Wenn der schnellere Zeiger das Ende der Liste erreicht, befindet sich der langsamere Zeiger in der Mitte:

public static Optional findMiddleElementFromHead1PassIteratively(Node head) { if (head == null) { return Optional.empty(); } Node slowPointer = head; Node fastPointer = head; while (fastPointer.hasNext() && fastPointer.next().hasNext()) { fastPointer = fastPointer.next().next(); slowPointer = slowPointer.next(); } return Optional.ofNullable(slowPointer.data()); }

Wir können diese Lösung mit einem einfachen Komponententest testen, indem wir Listen mit einer ungeraden und einer geraden Anzahl von Elementen verwenden:

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

3.3. Rekursiv das mittlere Element in einem Durchgang finden

Eine andere Möglichkeit, dieses Problem in einem Durchgang zu lösen, ist die Verwendung der Rekursion. Wir können bis zum Ende der Liste iterieren, um die Größe zu ermitteln, und in den Rückrufen zählen wir nur bis zur Hälfte der Größe.

Zu diesem Zweck erstellen wir in Java eine Hilfsklasse, um die Referenzen der Listengröße und des mittleren Elements während der Ausführung aller rekursiven Aufrufe beizubehalten:

private static class MiddleAuxRecursion { Node middle; int length = 0; }

Implementieren wir nun die rekursive Methode:

private static void findMiddleRecursively( Node node, MiddleAuxRecursion middleAux) { if (node == null) { // reached the end middleAux.length = middleAux.length / 2; return; } middleAux.length++; findMiddleRecursively(node.next(), middleAux); if (middleAux.length == 0) { // found the middle middleAux.middle = node; } middleAux.length--; }

Und schließlich erstellen wir eine Methode, die die rekursive Methode aufruft:

public static Optional findMiddleElementFromHead1PassRecursively(Node head) { if (head == null) { return Optional.empty(); } MiddleAuxRecursion middleAux = new MiddleAuxRecursion(); findMiddleRecursively(head, middleAux); return Optional.of(middleAux.middle.data()); }

Auch hier können wir es auf die gleiche Weise wie zuvor testen:

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

4. Fazit

In diesem Artikel haben wir das Problem des Findens des mittleren Elements einer verknüpften Liste in Java vorgestellt und verschiedene Lösungsmöglichkeiten aufgezeigt.

Wir haben mit dem einfachsten Ansatz begonnen, bei dem wir die Größe verfolgt haben, und danach haben wir mit den Lösungen fortgefahren, um das mittlere Element aus dem Hauptknoten der Liste zu finden.

Wie immer ist der vollständige Quellcode der Beispiele auf GitHub verfügbar.