Inverter uma Lista Ligada

Reverter uma Lista Encadeada é um problema interessante em estruturas de dados e algoritmos. Neste tutorial, discutiremos os vários algoritmos para reverter uma Lista Encadeada e depois implementá-los 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 para o elemento anterior e o 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 tem o endereço armazenado para isso. 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 inverter uma LinkedList iterativamente, precisamos armazenar as referências dos elementos seguinte e anterior, 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 inverter nossa LinkedList alterando as referências.

Os seguintes passos devem ser seguidos para inverter uma LinkedList. Crie 3 instâncias: atual, próximo, anterior. Repita o seguinte até que o atual NÃO seja 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 mais importante.
• Desloque o anterior para o atual.
• Desloque o elemento atual para o próximo.

No final, como o atual avançou uma posição além do último elemento, precisamos definir a cabeça para o último elemento que alcançamos. Isso está disponível em anterior. Defina a cabeça para 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 inverter 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 inverter uma Linked List iterativamente e imprimir seus elementos é dado 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 Encadeada Recursivamente

Para inverter uma LinkedList recursivamente, precisamos dividir a LinkedList 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 LinkedList recursivamente até o penúltimo elemento. Uma vez que alcançamos o último elemento, definimos isso como a cabeça. A partir daí, fazemos o seguinte até chegarmos ao início da LinkedList. node.next.next = node; node.next = null; Para não perder o rastro da cabeça original, vamos salvar uma cópia da instância da cabeça.

A seguir está a ilustração do procedimento acima. O programa Java para inverter uma LinkedList 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 LinkedList. Uma vez que alcançamos o final, definimos o penúltimo elemento como o próximo do último elemento e definimos o ponteiro próximo do penúltimo elemento como NULL. O último elemento será marcado como a nova cabeça. Use o seguinte código para inverter a lista encadeada usando a abordagem recursiva.

myLinkedList.head = recursiveReverse(myLinkedList.head);

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

Complexidade Espaço-Tempo da Reversão de uma Lista Encadeada

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

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