Inverter uma Lista Ligada

Reverter uma Lista Encadeada é um problema interessante em estrutura de dados e algoritmos. Neste tutorial, discutiremos os vários algoritmos para reverter uma Lista Encadeada e então os implementaremos usando Java.

Reverter uma Lista Encadeada

LinkedList é uma estrutura de dados que armazena os dados de maneira linear, embora não de maneira contígua. Cada elemento de uma LinkedList contém uma parte de dados e um endereço para o próximo elemento da LinkedList. Os elementos da LinkedList são popularmente conhecidos como nós.

A Doubly LinkedList armazena dois endereços: o endereço do elemento anterior e do próximo elemento.

Para reverter uma LinkedList no local, precisamos inverter os ponteiros de forma que o próximo elemento agora aponte para o elemento anterior. Segue a entrada e saída.

A cabeça da LinkedList é o primeiro nó. Nenhum outro elemento possui o endereço armazenado para este. A cauda da LinkedList é o último nó. O próximo endereço armazenado neste nó é null. Podemos reverter uma LinkedList de modo que a cabeça e a cauda também sejam alteradas usando:

• Abordagem Iterativa
• Abordagem Recursiva

Abordagem Iterativa para Reverter uma Lista Ligada

Para reverter uma LinkedList iterativamente, precisamos armazenar as referências dos elementos seguintes e anteriores, para que não se percam quando trocamos os ponteiros de endereço de memória para o próximo elemento na LinkedList. A ilustração a seguir demonstra como iremos reverter nossa LinkedList alterando as referências.

Os seguintes passos devem ser seguidos para reverter uma LinkedList. Crie 3 instâncias: atual, próximo, anterior. Repita o seguinte enquanto o atual NÃO for nulo:

• Salve o próximo nó do elemento atual no ponteiro próximo.
• Defina o próximo do Nó atual para o anterior. Esta é a linha MVP.
• Desloque o anterior para o atual.
• Desloque o elemento atual para o próximo.

No final, como o atual foi um lugar à frente do último elemento, precisamos definir a cabeça como o último elemento que alcançamos. Isso está disponível em anterior. Defina a cabeça como anterior. Assim, temos nossa nova cabeça da LinkedList, que é o último elemento da LinkedList anterior.

Aqui está uma implementação muito simples de LinkedList. Observe que esta não é uma implementação pronta para produção e a mantivemos simples para que nosso foco permaneça no algoritmo para reverter a 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;
		}
	}
}

O Programa Java para reverter uma Linked List de forma iterativa e imprimir seus elementos é apresentado abaixo:

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

}

Saída:

1 2 3 
3 2 1 

Inverter uma Lista Ligada Recursivamente

Para inverter uma Lista Ligada recursivamente, precisamos dividir a Lista Ligada em duas partes: cabeça e restante. A cabeça aponta inicialmente para o primeiro elemento. O restante aponta para o próximo elemento a partir da cabeça.

Travessamos a Lista Ligada recursivamente até o segundo último elemento. Uma vez que chegamos ao último elemento, definimos isso como a cabeça. A partir daí, fazemos o seguinte até chegarmos ao início da Lista Ligada. nó.próximo.próximo = nó; nó.próximo = nulo; Para não perder o rastro da cabeça original, salvamos uma cópia da instância da cabeça.

A seguinte é a ilustração do procedimento acima. O programa Java para inverter uma Lista Ligada recursivamente é:

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

Apenas passamos o head.next na chamada recursiva para ir até o final da Lista Ligada. Uma vez que chegamos ao final, definimos o segundo último elemento como o próximo do último elemento e definimos o ponteiro próximo do segundo último elemento como NULO. O último elemento será marcado como a nova cabeça. Use o seguinte código para inverter a lista ligada usando a abordagem recursiva.

myLinkedList.head = recursiveReverse(myLinkedList.head);

A saída permanecerá como na abordagem iterativa anterior.

Complexidade de Tempo e Espaço para Inverter uma Lista Ligada

Complexidade de Tempo – O(n) Complexidade de Espaço – O(1)

Você pode conferir o código completo e mais exemplos de Estruturas de Dados e Algoritmos em nosso Repositório no GitHub.