Invertire una Lista Collegata

Invertire una lista collegata è un problema interessante nella struttura dei dati e negli algoritmi. In questo tutorial, discuteremo i vari algoritmi per invertire una lista collegata e poi li implementeremo utilizzando Java.

Invertire una lista collegata

LinkedList è una struttura dati che memorizza i dati in modo lineare. Anche se non in modo contiguo. Ogni elemento di una LinkedList contiene una parte dei dati e un indirizzo dell’elemento successivo della LinkedList. Gli elementi di LinkedList sono popolarmente conosciuti come nodi.

La Doubly LinkedList memorizza due indirizzi. L’indirizzo dell’elemento precedente e successivo.

Per invertire una LinkedList sul posto, dobbiamo invertire i puntatori in modo che l’elemento successivo punti all’elemento precedente. Di seguito sono riportati l’input e l’output.

La testa della LinkedList è il primo nodo. Nessun altro elemento ha l’indirizzo memorizzato per questo. La coda della LinkedList è l’ultimo nodo. L’indirizzo successivo memorizzato in questo nodo è null. Possiamo invertire una LinkedList in modo che anche la testa e la coda cambino usando:

• Approccio iterativo
• Approccio ricorsivo

Approccio iterativo per invertire una Linked List

Per invertire una LinkedList in modo iterativo, è necessario memorizzare i riferimenti degli elementi successivi e precedenti, in modo che non vengano persi quando scambiamo i puntatori degli indirizzi di memoria con l’elemento successivo nella LinkedList. La seguente illustrazione mostra come invertire la nostra LinkedList modificando i riferimenti.

Ecco i passaggi da seguire per invertire una LinkedList. Creare 3 istanze: corrente, successivo, precedente. Eseguire il seguente ciclo finché corrente NON è null:

• Salvare il prossimo nodo dell’elemento corrente nel puntatore successivo.
• Impostare il puntatore next del nodo corrente al precedente. Questa è la linea MVP.
• Spostare il puntatore precedente al corrente.
• Spostare l’elemento corrente al successivo.

Alla fine, poiché il corrente è andato avanti di un posto rispetto all’ultimo elemento, è necessario impostare la testa sull’ultimo elemento raggiunto. Questo è disponibile in precedente. Impostare la testa su precedente. In questo modo otteniamo la nuova testa della LinkedList che è l’ultimo elemento della vecchia LinkedList.

Ecco una semplice implementazione di LinkedList. Notare che questa non è un’implementazione pronta per la produzione e l’abbiamo mantenuta semplice in modo che il nostro focus rimanga sull’algoritmo per invertire la LinkedList.

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

Di seguito è riportato il programma Java per invertire una LinkedList in modo iterativo e stampare i suoi elementi:

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 

Invertire una lista collegata in modo ricorsivo

Per invertire una lista collegata in modo ricorsivo, è necessario dividere la lista in due parti: la testa (head) e il resto (remaining). La testa punta al primo elemento inizialmente, mentre il resto punta all’elemento successivo alla testa.

Attraversiamo la lista collegata in modo ricorsivo fino all’ultimo elemento. Una volta raggiunto l’ultimo elemento, lo impostiamo come testa. Da lì, eseguiamo le seguenti operazioni fino a raggiungere l’inizio della lista. node.next.next = node; node.next = null; Per non perdere il riferimento alla testa originale, salveremo una copia dell’istanza della testa.

Ecco un’illustrazione della procedura descritta sopra. Il programma Java per invertire una lista collegata in modo ricorsivo è:

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

Nella chiamata ricorsiva, passiamo semplicemente head.next per andare alla fine della lista collegata. Una volta raggiunta la fine, impostiamo il penultimo elemento come successivo dell’ultimo elemento e impostiamo il puntatore successivo del penultimo elemento a NULL. L’ultimo elemento diventerà la nuova testa. Utilizza il seguente codice per invertire la lista collegata usando l’approccio ricorsivo.

myLinkedList.head = recursiveReverse(myLinkedList.head);

L’output sarà identico all’approccio iterativo precedente.

Complessità spazio-temporale per invertire una lista concatenata

Complessità temporale – O(n) Complessità spaziale – O(1)

Puoi controllare il codice completo e altri esempi di strutture dati e algoritmi nel nostro repository di GitHub.