Verkettete Liste umkehren

Das Umkehren einer verketteten Liste ist ein interessantes Problem in der Datenstruktur und Algorithmen. In diesem Tutorial werden wir die verschiedenen Algorithmen diskutieren, um eine verkettete Liste umzukehren und sie dann mit Java implementieren.

Verkettete Liste umkehren

Eine verkettete Liste ist eine Datenstruktur, die die Daten linear speichert, jedoch nicht auf zusammenhängende Weise. Jedes Element einer verketteten Liste enthält einen Datenteil und eine Adresse zum nächsten Element der verketteten Liste. Die Elemente einer verketteten Liste werden allgemein als Knoten bezeichnet.

Doppelt verkettete Listen speichern zwei Adressen. Die Adresse für das vorherige Element und das nächste Element.

Um eine LinkedList an Ort und Stelle umzukehren, müssen wir die Zeiger umkehren, sodass das nächste Element nun auf das vorherige Element zeigt. Folgendes sind die Eingabe- und Ausgabedaten. Der Kopf der LinkedList ist der erste Knoten. Für kein anderes Element ist die Adresse dafür gespeichert. Das Ende der LinkedList ist der letzte Knoten. Die nächste Adresse, die in diesem Knoten gespeichert ist, ist null. Wir können eine LinkedList so umkehren, dass sich auch der Kopf und das Ende ändern, indem wir verwenden:

• Iterativer Ansatz
• Rekursiver Ansatz

Iterativer Ansatz zum Umkehren einer verketteten Liste

Um eine LinkedList iterativ umzukehren, müssen wir die Verweise auf die nächsten und vorherigen Elemente speichern, damit sie nicht verloren gehen, wenn wir die Speicheradresszeiger zum nächsten Element in der LinkedList tauschen. Die folgende Illustration zeigt, wie wir unsere LinkedList umkehren, indem wir die Verweise ändern.

Die folgenden Schritte sind zu befolgen, um eine LinkedList umzukehren. Erstelle 3 Instanzen: current, next, previous. Durchlaufe das Folgende, bis current NICHT null ist:

• Speichere den nächsten Knoten des aktuellen Elements im nächsten Zeiger.
• Setze das nächste des current-Knotens auf previous. Dies ist die MVP-Zeile.
• Verschiebe previous zu current.
• Verschiebe das aktuelle Element zu next.

Zum Schluss, da current einen Platz vor dem letzten Element gegangen ist, müssen wir den Kopf auf das letzte Element setzen, das wir erreicht haben. Dies ist in previous verfügbar. Setze den Kopf auf previous. So erhalten wir unseren neuen Kopf der LinkedList, der das letzte Element der älteren LinkedList ist.

Hier ist eine sehr einfache Implementierung einer LinkedList. Beachte, dass dies keine für die Produktion bereite Implementierung ist, wir haben sie einfach gehalten, damit unser Fokus auf dem Algorithmus zur Umkehrung der Linked List bleibt.

package com.journaldev.linkedlist.reverse;

public class MyLinkedList {

	public Node head;

	public static class Node {

		Node next;

		Object data;

		Node(Object data) {
			this.data = data;
			next = null;
		}
	}
}

Das Java-Programm zur iterativen Umkehrung einer Linked List und zum Drucken ihrer Elemente sieht folgendermaßen aus:

package com.journaldev.linkedlist.reverse;

import com.journaldev.linkedlist.reverse.MyLinkedList.Node;

public class ReverseLinkedList {

	public static void main(String[] args) {
		MyLinkedList myLinkedList = new MyLinkedList();
		myLinkedList.head = new Node(1);
		myLinkedList.head.next = new Node(2);
		myLinkedList.head.next.next = new Node(3);

		printLinkedList(myLinkedList);
		reverseLinkedList(myLinkedList);
		printLinkedList(myLinkedList);

	}

	public static void printLinkedList(MyLinkedList linkedList) {
		Node h = linkedList.head;
		while (linkedList.head != null) {
			System.out.print(linkedList.head.data + " ");
			linkedList.head = linkedList.head.next;
		}
		System.out.println();
		linkedList.head = h;
	}

	public static void reverseLinkedList(MyLinkedList linkedList) {
		Node previous = null;
		Node current = linkedList.head;
		Node next;
		while (current != null) {
			next = current.next;
			current.next = previous;
			previous = current;
			current = next;
		}
		linkedList.head = previous;
	}

}

Ausgabe:

1 2 3 
3 2 1 

Eine verkettete Liste rekursiv umkehren

Um eine verkettete Liste rekursiv umzukehren, müssen wir die Liste in zwei Teile aufteilen: „head“ und „remaining“. „Head“ zeigt anfangs auf das erste Element. „Remaining“ zeigt auf das nächste Element nach „Head“.

Wir durchlaufen die verkettete Liste rekursiv, bis wir das vorletzte Element erreichen. Sobald wir das letzte Element erreicht haben, setzen wir es als „head“. Von dort aus machen wir folgendes, bis wir den Anfang der Liste erreichen. node.next.next = node; node.next = null; Um den ursprünglichen „head“ nicht zu verlieren, speichern wir eine Kopie der „head“-Instanz.

Die folgende Abbildung zeigt das oben beschriebene Verfahren. Das Java-Programm zum rekursiven Umkehren einer verketteten Liste lautet:

public static Node recursiveReverse(Node head) {
	Node first;

	if (head==null || head.next == null)
		return head;

	first = recursiveReverse(head.next);
	head.next.next = head;
	head.next = null;

	return first;
}

In dem rekursiven Aufruf geben wir einfach „head.next“ weiter, um zum Ende der Liste zu gelangen. Sobald wir das Ende erreicht haben, setzen wir das vorletzte Element als „next“ des letzten Elements und setzen den „next“-Zeiger des vorletzten Elements auf NULL. Das letzte Element wird als neuer „head“ markiert. Verwenden Sie den folgenden Code, um die verkettete Liste mit dem rekursiven Ansatz umzukehren.

myLinkedList.head = recursiveReverse(myLinkedList.head);

Die Ausgabe bleibt dieselbe wie beim vorherigen iterativen Ansatz.

Zeit- und Speicherkomplexität des Umkehrens einer verketteten Liste

Zeitkomplexität – O(n) Speicherkomplexität – O(1)

Sie können den vollständigen Code und weitere DS & Algorithmusbeispiele aus unserem GitHub-Repository überprüfen.