Invertir una Lista Enlazada

Revertir una lista enlazada es un problema interesante en estructuras de datos y algoritmos. En este tutorial, discutiremos varios algoritmos para revertir una Lista Enlazada y luego los implementaremos utilizando Java.

Revertir una Lista Enlazada

LinkedList es una estructura de datos que almacena la información de manera lineal, aunque no de manera contigua. Cada elemento de una LinkedList contiene una parte de datos y una dirección al siguiente elemento de la LinkedList. Los elementos de LinkedList son comúnmente conocidos como nodos.

La LinkedList doble almacena dos direcciones: una para el elemento anterior y otra para el siguiente elemento.

Para invertir una LinkedList en su lugar, necesitamos revertir los punteros de manera que el siguiente elemento ahora apunte al elemento anterior. A continuación se muestra la entrada y la salida. La cabeza de la LinkedList es el primer nodo. Ningún otro elemento tiene almacenada la dirección para esto. La cola de la LinkedList es el último nodo. La dirección siguiente almacenada en este nodo es null. Podemos invertir una LinkedList de manera que la cabeza y la cola también cambien utilizando:

• Enfoque Iterativo
• Enfoque Recursivo

Enfoque Iterativo para Invertir una Lista Enlazada

Para revertir una LinkedList de forma iterativa, necesitamos almacenar las referencias de los elementos siguiente y anterior, para que no se pierdan cuando intercambiamos los punteros de dirección de memoria al siguiente elemento en la LinkedList. La siguiente ilustración muestra cómo revertiremos nuestra LinkedList cambiando las referencias.

A continuación se presentan los pasos a seguir para revertir una LinkedList. Cree 3 instancias: actual, siguiente, anterior. Itere lo siguiente hasta que el actual NO sea nulo:

• Guarde el siguiente Nodo del elemento actual en el puntero siguiente.
• Establezca el siguiente del Nodo actual en el anterior. Esta es la línea MVP.
• Mueva el anterior al actual.
• Mueva el elemento actual al siguiente.

Al final, dado que el actual ha avanzado un lugar más allá del último elemento, necesitamos establecer el inicio en el último elemento que alcanzamos. Esto está disponible en anterior. Establezca el inicio en anterior. Así tenemos nuestro nuevo inicio de la LinkedList que es el último elemento de la LinkedList anterior.

A continuación, se muestra una implementación muy simple de LinkedList. Tenga en cuenta que esta no es una implementación lista para producción y la hemos mantenido simple para que nuestro enfoque permanezca en el algoritmo para revertir la Linked List.

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

El programa Java para revertir una Linked List de forma iterativa e imprimir sus elementos se muestra a continuación:

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

}

Salida:

1 2 3 
3 2 1 

Revertir una lista enlazada de forma recursiva

Para revertir una lista enlazada de forma recursiva, necesitamos dividir la lista en dos partes: cabeza y resto. La cabeza apunta inicialmente al primer elemento. El resto apunta al siguiente elemento desde la cabeza.

Recorremos la lista enlazada de forma recursiva hasta el segundo último elemento. Una vez que hemos alcanzado el último elemento, lo establecemos como la cabeza. A partir de ahí, hacemos lo siguiente hasta llegar al inicio de la lista enlazada. node.next.next = node; node.next = null; Para no perder el rastro de la cabeza original, guardaremos una copia de la instancia de la cabeza.

A continuación se ilustra el procedimiento anterior. El programa Java para revertir una lista enlazada de forma recursiva es:

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

Solo pasamos head.next en la llamada recursiva para ir al final de la lista enlazada. Una vez que llegamos al final, establecemos el penúltimo elemento como el siguiente del último elemento y establecemos el puntero siguiente del penúltimo elemento en NULL. El último elemento se marcará como la nueva cabeza. Utilice el siguiente código para revertir la lista enlazada usando el enfoque recursivo.

myLinkedList.head = recursiveReverse(myLinkedList.head);

La salida permanecerá igual que en el enfoque iterativo anterior.

Complejidad Temporal del Reverso de una Lista Enlazada

Complejidad Temporal – O(n) Complejidad Espacial – O(1)

Puedes revisar el código completo y más ejemplos de Estructuras de Datos y Algoritmos en nuestro Repositorio de GitHub.