Leetcode 206 – Reverse Linked List – Solução

O problema Leetcode 206, intitulado Reverse Linked List, ou algo como “Reversão de lista encadeada” em português é um dos problemas mais fomosos do Leetcode. Ele faz parte da famosa lista Blind 75, que contém problemas comuns em entrevistas de emprego de grandes empresas de tecnologia, como Google, Facebook etc.

Neste post eu irei explicar como resolvê-lo, e irei mostrar a solução usando Python.

Enunciado do problema – Leetcode 206

Dado o nó de início head de uma lista encadeada unidirecional, reverta a lista e retorne a lista revertida.

Exemplo 1:

Entrada: head = [1,2,3,4,5]
Saída: [5,4,3,2,1]

Example 2:

Entrada: head = [1,2]
Saída: [2,1]

Example 3:

Entrada: head = [] (lista vazia)
Saída: []

Condições do problema:

# Definição da lista encadeada simples.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

• O número de nós na lista pertence ao intervalo [0, 5000].
• -5000 <= Node.val <= 5000

Bônus: Uma lista encadeada pode ser revertida iterativa ou recursivamente. Você conseguiria implementar ambas as soluções?

Solução explicada

A primeira coisa que precisamos fazer para resolver esse problema é ter certeza que entendemos o seu enunciado. O que é esperado de nós? Devemos retornar o último nó da lista original, que será o head da lista revertida.

Entendido isso, passemos ao passo seguinte: por onde comeamos, pelo início ou pelo fim da lista? A resposta a essa pergunta, nesse problema, é simples, pois nos é dito no enunciado do problema que possuímos apenas o nó inicial da lista, head – comecemos, portanto, pelo início da lista. Para obtermos o último nó da lista para então poder começar pelo seu fim, é preciso percorrê-la por inteiro, o que adicionaria operações desnecessárias ao nosso algoritmo e o tornaria menos eficiente.

Ok, começaremos pelo início, mas como começamos? Bom, sabemos que o primeiro nó da lista deve se tornar o seu último nó, e que o segundo deve apontar para o primeiro; em seguida, o terceiro deve apontar para o segundo, o quarto para o terceiro, e assim por diante até que o último aponte para o penúltimo e torne-se a nova cabeça da lista. Vejamos na figura abaixo o procedimento de reversão das cadeias da lista para os três primeiros nós.

O procedimento acima parece correto e bastante simples, não? Todavia, ele possui um pequeno problema – vejamos qual ele é. Suponhamos que estamos no segundo nó da lista e precisamos fazê-lo apontar para o nó inicial. É necessário, portanto, guardar a informação do nó anterior (o nó inicial, nesse caso) para poder fornecê-la ao nó atual. Até aqui tudo bem, precisamos de uma variável auxiliar para guardar a informação do nó anterior.

Contudo, o que acontece quando fazemos com que o nó número 2 da nossa figura acima aponte para o nó de número 1? A conexão entre os nós 2 e 3 se perde e com ela perdemos nós a capacidade de avançar na lista para o nó de número 3, pois para avançarmos na lista nós usamos o nó para o qual o nó atual aponta. E agora, como resolvemos esse problema? A solução aqui também é simples: precisamos de mais uma variável auxiliar.

Assim sendo, precisamos no total de 2 variáveis auxiliares que chamarei de prev e nextNode, responsáveis por armazenar, respectivamente, o nó anterior ao atual e aquele para o qual o atual aponta antes que a sua cadeia seja revertida. A figura abaixo ilustra o uso desses dois nós na reversão da cadeia no nível do nó 2 da figura 1.

Note que para o correto funcionamento do algoritmo é necessário usar uma outra variável auxiliar chamada curr. Essa variável guarda o nó atual que está sendo manipulado, e também representa o próximo nó a ser manipulado na repetição seguinte. Sem ela nós perderiamos a informação do nó atual – que deverá ser o prev da próxima iteração do algoritmo – no passo 1.1 da figura acima.

De maneira resumida, o algorítmo usado para reverter a lista encadeada usando uma solução recursiva é aquele mostrado a seguir:

1. Atribuir à variável curr o nó seguinte ao inicial (head.next);
2. Invocar a função de reversão (que chamarei de recurse) passando o nó head como o prev e o nó curr já modificado de acordo com o passo 1;
3. Verificar se o nó seguinte ao atual, ou seja, curr.next está vazio; se sim, chegamos ao fim da lista e os passos a seguir devem ser executados:
   1. faça curr.next apontar para o nó anterior (prev);
   2. retorne o novo nó inicial, curr;
4. Se não tivermos chegado ao fim da lista, siga as seguintes etapas:
   1. armazene o valor do próximo nó (curr.next) na variável auxiliar nextNode;
   2. Faça o nó atual apontar para o nó anterior: que curr.next aponte para prev;
   3. Substitua o valor anterior de prev pelo nó atual, ou seja, por curr;
   4. chame a função recurse novamente passando como argumentos prev e nextNode. Atenção: o segundo argumento é nextNode e não curr.

Código – Python

Agora que entendemos a visão geral da solução, passemos ao código da solução. Em adição à solução recursiva, todavia, escrevi também o código da solução iterativa logo a seguir.

---

Leetcode 206 – solução recursiva

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        
        def recurse(prev, curr) -> ListNode:
            if curr.next is None:
                curr.next = prev
                return curr
            nextNode = curr.next
            curr.next = prev
            prev = curr
            return recurse(prev, nextNode)
        
        curr = head.next
        head.next = None

        return recurse(head, curr)

---

Leetcode 206 – solução iterativa

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        
        curr = head.next
        head.next = None
        prev = head

        while curr.next is not None:
            nextNode = curr.next
            curr.next = prev
            prev = curr
            curr = nextNode

        curr.next = prev
        return curr

---

Conclusão

Espero tê-lo ajudado a entender esse problema tão famoso que é o Leetcode 206 – Reverse Linked List. Como sempre, gosto de lembrar que se você tiver encontrado outra forma de resolver o problema, ou talvez uma forma mais eficiente de fazê-lo, por favor me diga nos comentários que eu ficarei feliz em adicioná-la ao conteúdo do texto.

Além disso, se quiser ver mais artigo acerca de Leetcode com soluções e exemplos explicados, você pode começar clicando no link abaixo para ver a solução do problema Leetcode 57 – Insert Interval. Boa leitura!

Leetcode 57 – Insert Interval »