Inverter uma lista encadeada simples é um problema clássico em estruturas de dados que envolve a manipulação de ponteiros para reordenar os nós da lista. O objetivo é transformar uma lista como 1 -> 2 -> 3 -> 4 -> 5 -> None em 5 -> 4 -> 3 -> 2 -> 1 -> None.

Compreendendo a Enversão

Uma lista encadeada consiste em uma sequência de nós, onde cada nó contém um valor e um ponteiro (ou referência) para o próximo nó na sequência. O último nó aponta para None (ou null). Inverter a lista significa que o primeiro nó se torna o último, o segundo o penúltimo, e assim por diante, com todos os ponteiros "próximo" apontando na direção oposta. O nó que era o último na lista original se tornará o novo cabeçalho.

Abordagem Iterativa

A forma mais comum de inverter uma lista encadeada é através de uma abordagem iterativa, que envolve a utilização de três ponteiros para manter o controle dos nós durante o processo de inversão. Estes ponteiros são:

• no_anterior (anterior): Aponta para o nó que já foi invertido e agora está "atrás" do nó atual na nova sequência.
• no_atual (atual): Aponta para o nó que está sendo processado no momento, cujo ponteiro proximo será invertido.
• proximo_original (temporário para o próximo): Armazena temporariamente a referência para o nó seguinte na lista original, antes que o ponteiro proximo do no_atual seja modificado.

O algoritmo itera através da lista, nó por nó. Em cada passo, o ponteiro proximo do no_atual é modificado para apontar para o no_anterior, efetivamente "invertendo" a direção. Em seguida, os ponteiros são avançados para processar o próximo nó.

Definição de Nó

Para contextualizar, um nó de uma lista encadeada simples em Python pode ser definido da seguinte forma:

class ListNode:
    def __init__(self, valor=0, proximo=None):
        self.valor = valor
        self.proximo = proximo

Implementação do Algoritmo

A seguir, o código Python para a inversão iterativa de uma lista encadeada:

from typing import Optional

class ListNode:
    def __init__(self, valor=0, proximo=None):
        self.valor = valor
        self.proximo = proximo

class Solution:
    def inverterLista(self, cabeca: Optional[ListNode]) -> Optional[ListNode]:
        # 'no_anterior' inicialmente é None. O primeiro nó da lista original (que se tornará o último
        # na lista invertida) terá seu ponteiro 'proximo' apontando para None.
        no_anterior = None

        # 'no_atual' começa no cabeçalho da lista. Este é o nó que estamos processando atualmente.
        no_atual = cabeca

        # Itera enquanto houver nós para processar na lista original.
        while no_atual:
            # 1. Guarda a referência do próximo nó original.
            # Isso é crucial para não perder o restante da lista original após
            # mudarmos o ponteiro 'proximo' do 'no_atual'.
            proximo_original = no_atual.proximo

            # 2. Inverte o ponteiro 'proximo' do 'no_atual'.
            # Agora, 'no_atual' aponta para o nó que era seu antecessor na lista original
            # (ou None, se for o primeiro nó a ser invertido).
            no_atual.proximo = no_anterior

            # 3. Avança 'no_anterior' para a posição do 'no_atual'.
            # O 'no_atual' já foi invertido, então ele se torna o novo 'no_anterior'
            # para o próximo passo da iteração.
            no_anterior = no_atual

            # 4. Avança 'no_atual' para o próximo nó original que foi salvo.
            # Continua para o próximo nó na lista que ainda precisa ser invertido.
            no_atual = proximo_original

        # Ao final do loop, 'no_atual' será None (indicando que todos os nós foram processados),
        # e 'no_anterior' estará apontando para o último nó que foi processado, que é o
        # novo cabeçalho da lista invertida.
        return no_anterior