Draai een Gelinkte Lijst om

Het omkeren van een Gekoppelde Lijst is een interessant probleem in datastructuren en algoritmen. In deze tutorial zullen we de verschillende algoritmen bespreken om een Gekoppelde Lijst om te keren en ze vervolgens implementeren met behulp van Java.

Keer een Gekoppelde Lijst om

Een Gekoppelde Lijst is een datastructuur die gegevens op een lineaire manier opslaat, zij het niet op een aaneengesloten manier. Elk element van een Gekoppelde Lijst bevat een gegevensdeel en een verwijzing naar het volgende element van de Gekoppelde Lijst. Elementen van een Gekoppelde Lijst staan bekend als knooppunten.

Dubbel Gekoppelde Lijsten slaan twee adressen op: het adres van het vorige element en het volgende element.

Om een LinkedList ter plaatse om te keren, moeten we de pointers omkeren, zodat het volgende element nu wijst naar het vorige element. Hier is de invoer en uitvoer. Het hoofd van de LinkedList is het eerste knooppunt. Geen ander element heeft het adres opgeslagen voor dit knooppunt. De staart van de LinkedList is het laatste knooppunt. Het volgende adres opgeslagen in dit knooppunt is null. We kunnen een LinkedList omkeren zodat het hoofd en de staart ook veranderen met behulp van:

• Iteratieve Aanpak
• Recursieve Aanpak

Iteratieve Aanpak om een Linked List om te keren

Om een LinkedList iteratief om te keren, moeten we de verwijzingen van de volgende en vorige elementen opslaan, zodat ze niet verloren gaan wanneer we de geheugenadres pointers naar het volgende element in de LinkedList omwisselen. De volgende illustratie toont hoe we onze LinkedList zullen omkeren door de verwijzingen te wijzigen.

De volgende stappen moeten worden gevolgd om een LinkedList om te keren. Maak 3 instanties: huidige, volgende, vorige. Herhaal de volgende stappen totdat huidige NIET null is:

• Bewaar de volgende Node van het huidige element in de volgende pointer.
• Stel de volgende van de huidige Node in op de vorige. Dit is de MVP-regel.
• Verplaats vorige naar huidige.
• Verplaats het huidige element naar volgende.

Tenslotte, aangezien het huidige één plaats voor het laatste element is gegaan, moeten we de kop instellen op het laatste element dat we hebben bereikt. Dit is beschikbaar in vorige. Zet de kop op vorige. Zo hebben we onze nieuwe kop van de LinkedList, die het laatste element is van de oudere LinkedList.

Hier is een zeer eenvoudige implementatie van LinkedList. Let op dat dit geen implementatie is die klaar is voor productie en we hebben het eenvoudig gehouden zodat onze focus ligt op het algoritme om de Linked List om te keren.

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;
		}
	}
}

Het Java-programma om een Linked List iteratief om te keren en de elementen af te drukken, wordt hieronder gegeven:

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;
	}

}

Output:

1 2 3 
3 2 1 

Herhaal een Linked List Recursief

Om een LinkedList recursief om te keren, moeten we de LinkedList in twee delen verdelen: hoofd en resterend. Het hoofd wijst aanvankelijk naar het eerste element. Resterend wijst naar het volgende element vanaf het hoofd.

We doorlopen de LinkedList recursief tot het op een na laatste element. Zodra we het laatste element hebben bereikt, stellen we dat in als het hoofd. Vanaf daar doen we het volgende totdat we het begin van de LinkedList bereiken. node.next.next = node; node.next = null; Om het oorspronkelijke hoofd niet uit het oog te verliezen, zullen we een kopie van het hoofdinstance opslaan.

Hieronder staat de illustratie van de bovenstaande procedure. Het Java-programma om een LinkedList recursief om te keren is:

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;
}

We geven gewoon het hoofd.next door in de recursieve oproep om naar het einde van de LinkedList te gaan. Zodra we het einde bereiken, stellen we het op een na laatste element in als het volgende van het laatste element en stellen we de volgende pointer van het op een na laatste element in op NULL. Het laatste element wordt gemarkeerd als het nieuwe hoofd. Gebruik de volgende code om de linked list om te keren met de recursieve aanpak.

myLinkedList.head = recursiveReverse(myLinkedList.head);

De uitvoer blijft hetzelfde als bij de vorige iteratieve benadering.

Tijd- en Ruimtecomplexiteit van het Omkeren van een Gekoppelde Lijst

Tijdcomplexiteit – O(n) Ruimtecomplexiteit – O(1)

Je kunt de volledige code en meer voorbeelden van DS & Algoritmes bekijken op onze GitHub Repository.