Como Reverter uma Lista Encadeada em Python

Ricardo Poffo

Listas encadeadas são estruturas de dados onde um conjunto de nós ligados um ao outro formam uma sequência.

“In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next.” - Wikipedia

Reverter uma lista encadeada é um problema clássico de estrutura de dados. Neste tutorial, vamos explorar como reverter uma lista encadeada em Python, passo a passo, com uma explicação detalhada e um exemplo prático. Esse tipo de operação é comum em entrevistas técnicas para cargos de desenvolvedor de software como engenheiro de software backend.

Definição de um Nó

Uma lista encadeada é composta por nós, onde cada nó contém um valor e uma referência para o próximo nó. Vamos começar definindo a estrutura básica de um nó em Python:

class ListNode:
    def __init__(self, value=0, next=None):
        self.value = value
        self.next = next

Função para Reverter a Lista Encadeada

Para reverter uma lista encadeada, precisamos alterar as referências de cada nó para que apontem para o nó anterior ao invés do próximo. Aqui está como podemos implementar isso:

def reverse_linked_list(head):
    prev = None
    current = head
    
    while current:
        next_node = current.next  # Salva a referência ao próximo nó
        current.next = prev       # Inverte a direção da seta (link)
        prev = current            # Move o ponteiro prev para frente
        current = next_node       # Move para o próximo nó na lista original
        
    return prev  # No final, prev será o novo head da lista invertida

Explicação Passo a Passo

  1. Inicialização:

    • prev é inicializado como None, porque o novo fim da lista deve apontar para None.
    • current é inicializado como head, o início da lista original.

  2. Iteração:

    • Enquanto current não for None (ou seja, até chegarmos ao fim da lista):
    • next_node armazena a referência ao próximo nó (current.next).
    • current.next é atualizado para prev, invertendo a direção da seta.
    • prev é movido para current, fazendo com que o nó atual se torne o anterior na próxima iteração.
    • current é movido para next_node, o próximo nó da lista original.

  3. Retorno:

    • No final do loop, prev será o novo head da lista invertida.

Exemplo Prático

Vamos ver um exemplo de como usar essa função para reverter uma lista encadeada.

Criando uma Lista Encadeada

Primeiro, criaremos uma função auxiliar para converter uma lista Python em uma lista encadeada:


def create_linked_list(lst):
    head = ListNode(lst[0])
    current = head
    for value in lst[1:]:
        current.next = ListNode(value)
        current = current.next
    return head

Essa função recebe uma lista como entrada e retorna a cabeça da lista encadeada criada.

Função para Imprimir a Lista Encadeada

Para facilitar a visualização, criaremos também uma função para imprimir a lista encadeada:


def print_linked_list(head):
    current = head
    while current:
        print(current.value, end=" -> " if current.next else "\n")
        current = current.next

Essa função percorre a lista encadeada a partir da cabeça (head) e imprime os valores dos nós.

Código Completo

Agora, vamos utilizar essas funções para criar e reverter uma lista encadeada:

# Criando uma lista encadeada: 1 -> 2 -> 3 -> 4 -> 5
head = create_linked_list([1, 2, 3, 4, 5])

print("Original:")
print_linked_list(head)

# Revertendo a lista encadeada
reversed_head = reverse_linked_list(head)

print("Revertida:")
print_linked_list(reversed_head)

Saída Esperada

Ao executar o código acima, a saída deve ser:

Original:
1 -> 2 -> 3 -> 4 -> 5
Revertida:
5 -> 4 -> 3 -> 2 -> 1

Conclusão

Reverter uma lista encadeada é um problema comum em disciplinas de algoritmos e estrutura de dados. Também é comum em entrevistas técnicas para aferir sua compreensão de estruturas de dados e manipulação de referências. Com a abordagem apresentada, você pode reverter eficientemente uma lista encadeada com complexidade de tempo O(n) e complexidade de espaço O(1), utilizando apenas algumas variáveis adicionais.

Espero que este tutorial tenha sido útil! Se você tiver alguma dúvida ou sugestão, sinta-se à vontade para enviar uma mensagem.