LeetCode 143. Reorder List (Reordenamento de Lista)
Inaugurando um novo tipo de conteúdo aqui no blog, dessa vez eu vou resolver um típico problema de entrevista de emprego usando Python! O problema é esse daqui: https://leetcode.com/problems/reorder-list/ e, segundo algumas consultas, ele já apareceu em processos seletivos para o Google, Facebook, Amazon, Linkedin, dentre outros...
Sobre o que é o problema?
A ideia é simples. Dada uma lista encadeada simples como esta abaixo:
Reordená-la conforme o exemplo:
Lembrando que você não deve mudar o conteúdo dos nós, mas apenas reordenar em relação ao original.
Seguem 2 exemplos para ajudar a entender:
Entrada: head = [1,2,3,4]
Saída: [1,4,3,2]
Entrada: head = [1,2,3,4,5]
Saída: [1,5,2,4,3]
Vixi, como resolve?
A princípio não é um problema difícil de resolver se você tiver uma boa noção de Estruturas de Dados, ainda que exija um pouco de criatividade para criar uma solução eficiente.
Hora de colocar a mão na massa!
1º Passo: Criar código de Lista Simplesmente Encadeada.
Para começar, já que se trata de uma lista, vamos criar uma classe Node:
class Node:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return self.val
Definimos o construtor (isso é feito por meio das palavras-chave def __init__) fazendo com que eles recebam duas informações fundamentais a um nó qualquer: seu conteúdo (ilustrado por um inteiro val) e um objeto next que irá apontar para o próximo nó da sequência.
O que pode gerar estranhamento no código acima, é o método __repr__. Por meio dele, você define o que "imprimir" caso mande "printar" um objeto da classe Node. Acho que o exemplo abaixo é autoexplicativo:
n = Node("1")
print("Esse nó tem o valor:", n)
Esse nó tem o valor: 1
Não queria me prolongar falando sobre, mas o __repr__ é tipicamente usado para fins de depuração por parte do programador quando o Python precisa "resolver" um objeto como se fosse texto. Em nosso projeto vai ser importante para verificar o resultado quando for necessário.
Vamos então ao código da lista encadeada simples de fato.
class LinkedList:
def __init__(self):
self.head = None
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.val)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
def add(self, node):
if self.head is None:
self.head = node
return
for current_node in self:
pass
current_node.next = node
Para entender o código acima, eu acho importante a leitura de algum livro de Estrutura de Dados sobre listas simplesmente encadeadas. No entanto, para resumir:
No construtor __init__ inicializamos a "cabeça" (head) da lista como vazia;
Em __repr__ definimos o jeito de apresentar na tela todos os nós da lista em ordem. A variável node serve como um auxiliar que atuará como um ponteiro "caminhando" pela lista; nodes, por sua vez, será uma lista temporária que vai adicionar na ordem o conteúdo de cada nó para depois mostrarmos na tela; o laço while serve para "andarmos" pela lista adicionando nó após nó em nodes, até que cheguemos no final dela e return " -> ".join(nodes) vai "juntar" os nós e mostrá-los separados com setas (veja o exemplo de código abaixo para entender);
__iter__ é o método que permite implementar o que acontece quando você tenta "iterar" pela lista, por exemplo, usando laço for ou while. O while de __repr__ só funciona devido a essa implementação (e para entender melhor o código, sugiro que você leia o texto sobre Geradores e Iteradores);
O método add insere um nó ao final da lista. Se a lista estiver vazia, você "entra" no primeiro if (if self.head is None). Se não, você "percorre" a lista até chegar na última posição por meio do for current_node in self: (que novamente só funciona graças a implementação de __iter__), fazendo com que o nó node seja o next do último (que se torna penúltimo) nó da lista (linha 26).
Veja um exemplo desse código em ação:
l = LinkedList()
l.add(Node("1"))
l.add(Node("2"))
l.add(Node("3"))
l.add(Node("4"))
l.add(Node("5"))
print(l)
Saída: 1 -> 2 -> 3 -> 4 -> 5 -> None
2º Passo: Obter o ponto médio da Lista.
É importante lembrar que não basta resolver o problema, mas buscar um meio eficiente de se fazer isso.
Quando eu elaborei o primeiro raciocínio para esse exercício, pensei no seguinte: a partir do "ponto médio" da lista (ou seja, o nó que encontra-se na metade e que na animação abaixo está apontado pela seta vermelha) "caminhar" até a última posição. No exemplo [1->2->3->4->5], o 3 é o "ponto médio" e a última posição é o nó com o valor 5.
Chegando lá, eu tiro o último nó da fila e o insiro após o primeiro nó, ficando a configuração [1->5->2->3->4]. A seguir, repetiria esse procedimento pegando novamente o último nó (que agora é o 4), o insiro após o terceiro da esquerda para a direita [1->5->2->4->3] e assim sucessivamente, até que o nó que estava no ponto médio se torne o último.
Veja a animação abaixo para entender o procedimento (abaixo você pode ver ela tanto em gif quanto no youtube).
Na prática implementar o procedimento acima é suficiente para reordenar, mas ele tem um problema: custo computacional. Repare que para cada vez que eu "troco" o nó da última posição por outro, eu preciso "andar" da metade da lista até o fim (na última seção desse texto eu discuto a complexidade de tempo disso). Para uma lista pequena isso não é um problema, mas para uma lista com milhares ou milhões de elementos, isso vai fazer muita diferença.
Se você implementar conforme eu exemplifiquei na animação acima, o leetcode vai recusar sua solução alegando que ela é lenta (e é mesmo). Assim, vamos precisar de outra estratégia mais esperta.
De qualquer forma, precisamos "achar" o ponto médio da lista e isso pode ser feito fazendo o seguinte: contando quantos nós a lista tem e anotando qual a posição do ponto médio (ver código abaixo).
#1. quantos nós no total a lista tem?
aux_p = l.head
total = 0
while aux_p is not None:
aux_p = aux_p.next
total += 1
#2. pegar posição do ponto médio (na lista [1->2->3->4->5], este será 2 (assumindo que 0 é o primeiro nó, 1 será o segundo e 2 é o terceiro nó)
midpoint = total//2
#3. apontar no elemento da posição média
med_pointer = l.head
for counter in range(midpoint):
med_pointer = med_pointer.next
No código do 1º comentário, a gente percorre toda a lista no laço while, sempre somando mais 1 na variável total para contar quantos nós a lista l possui.
O 2º comentário é simples e direto: qual a posição do ponto médio da lista? No caso da lista [1->2->3->4->5] essa posição é 2 referente ao nó 3 (assumindo que 0 seja a primeira posição, 1 é a segunda posição e 2 é a terceira posição). Esse valor é guardado em midpoint.
Finalmente, no código do 3º comentário vamos fazer com que o ponteiro med_pointer aponte para a posição da metade da lista. O for assume um papel parecido com o while dos trechos anteriores, só que "parando" na metade.
Vamos pegar a lista de exemplo e ver as saídas esperadas.
#0. criando a lista [1->2->3->4->5]
l = LinkedList()
l.add(Node("1"))
l.add(Node("2"))
l.add(Node("3"))
l.add(Node("4"))
l.add(Node("5"))
#1. quantos nós no total a lista tem?
aux_p = l.head
total = 0
while aux_p is not None:
aux_p = aux_p.next
total += 1
#2. pegar posição do ponto médio (na lista [1->2->3->4->5], o ponto médio será 2 (assumindo que 0 é a primeira posição, 1 será a segunda...)
midpoint = total//2
#3. apontar no elemento da posição média
med_pointer = l.head
for counter in range(midpoint):
med_pointer = med_pointer.next
#4. imprimir as informações na tela
print("O total de elementos de l é:", total)
print("O nó da metade é (0 é a primeira posição):", midpoint)
print("Nó do ponto médio tem o valor:", med_pointer)
O total de elementos de l é: 5
O nó da metade é (0 é a primeira posição): 2
Nó do ponto médio tem o valor: 3
3º Passo: "Inverter" as referências do ponto médio em diante
Quê? O que esse título quer dizer???
Como falei antes, precisamos de uma estratégia inteligente para apontar sempre para o último nó da lista sem percorrer a metade várias vezes, como mencionei na seção anterior. Lembre-se que você não pode mudar o conteúdo dos nós, mas ninguém falou nada sobre mudar as referências (o atributo next de cada nó).
Vamos fazer o seguinte: "inverter" os apontamentos dos nós do ponto médio em diante, conforme a animação abaixo:
O motivo de fazermos isso é simples: reduzir o custo computacional de "andar" pela lista enquanto trocamos o nó da última posição para inserirmos após o primeiro nó, seguido de novamente trocar o último nó para inserir após o terceiro nó e assim sucessivamente. Além disso, vamos guardar uma referência para o último nó da lista em last_pointer (veja o código abaixo).
#4. "inverter" as referências do ponto médio em diante...
bef = med_pointer
curr = med_pointer.next
aft = med_pointer.next.next
curr.next = bef
while aft is not None:
bef = curr
curr = aft
aft = aft.next
curr.next = bef
last_pointer = curr
É difícil entender o código acima se você mesmo não "desenhar" no papel o que está acontecendo. Inclusive, isso é algo fundamental em Estrutura de Dados no geral: desenhar o que está acontecendo.
De qualquer forma, o vídeo abaixo mostra passo a passo o que o código acima faz e eu recomendo assistí-lo para entender!
Basicamente o ponteiro curr muda as referências do nó analisado no momento e as referências bef e aft, respectivamente, guarda os apontamentos de antes e depois do nó curr. Precisamos delas de "backup" enquanto fazemos as trocas. Finalmente, o laço while faz com que "caminhemos" pela lista fazendo as correções devidas.
4º Passo - Inserir o último nó após o 1º, depois inserir o (próximo) último nó após o 3º e assim sucessivamente...
Agora que estamos apontando para o último nó (por meio do last_pointer) e temos uma "estrada" do último nó para o penúltimo e antepenúltimo, podemos "ir caminhando" trocando os nós para as posições desejadas.
Para sermos práticos, podemos fazer o seguinte. Temos o seguinte código:
first_pointer = llist.head
while med_pointer != la_pointer:
last_prev = last_pointer.next
first_next = first_pointer.next
first_pointer.next = last_pointer
last_pointer.next = first_next
first_pointer = first_pointer.next.next
last_pointer = last_prev
med_pointer.next = None
Para entender o que o código acima está fazendo, sugiro que você assista ao vídeo abaixo. Em resumo, os ponteiros first_pointer e last_pointer começam no início e fim da lista. À medida que eles "vão andando" em sentidos opostos, eles vão "trocando" os nós de posição, até que eles "se encontrem", o que indica que a reordenação terminou e foi feita com sucesso.
First_pointer vai "saltar" de 2 em 2 nós servindo como marcação de onde o último nó da fila (em lase_pointer) vai "entrar". Os ponteiros first_next e last_prev são referências que precisamos para fazer as devidas trocas.
Código Final
Abaixo temos o código completo, que após algumas modificações funciona perfeitamente no leetcode (lembre-se de mudar o llist.head para head e o inserir na classe Solution).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __repr__(self):
return self.val
class LinkedList:
def __init__(self):
self.head = None
def __repr__(self):
node = self.head
nodes = []
while node is not None:
nodes.append(node.val)
node = node.next
nodes.append("None")
return " -> ".join(nodes)
def __iter__(self):
node = self.head
while node is not None:
yield node
node = node.next
def add_last(self, node):
if self.head is None:
self.head = node
return
for current_node in self:
pass
current_node.next = node
#-------a solução de fato---------
#1. quantos elementos a lista tem?
aux_p = llist.head
total = 0
while aux_p is not None:
aux_p = aux_p.next
total += 1
#2. pegar mediana (0 é primeira posição da lista, 1 é a segunda posição da lista...)
median = total//2
if total > 2:
#3. apontar no elemento da mediana
median_pointer = llist.head
for counter in range(median):
median_pointer = median_pointer.next
#4. "inverter" as referências da mediana em diante...
bef = median_pointer
curr = median_pointer.next
aft = median_pointer.next.next
curr.next = bef
while aft is not None:
bef = curr
curr = aft
aft = aft.next
curr.next = bef
last_pointer = curr
#5. fazer ponteiros "andarem" pela lista fazendo as trocas
first_pointer = llist.head
while median_pointer != last_pointer:
last_prev = last_pointer.next
first_next = first_pointer.next
first_pointer.next = last_pointer
last_pointer.next = first_next
first_pointer = first_pointer.next.next
last_pointer = last_prev
median_pointer.next = None
Apenas uma pequena mudança foi necessária: incluir toda a solução dentro do if total > 2: (linha 48). Isso é necessário pois não faz sentido reordenar essa lista se ela for muito pequena. A operação de reordenação só faz sentido se houver ao menos 3 nós na lista.
Breve discussão sobre complexidade
O primeiro raciocínio que apresentei no 2º Passo, em que a lista permanece orientada em uma mesma direção (1->2->3->4->5) acrescenta um passo extra que obrigaria sempre "caminhar" do ponto médio até o nó final da lista, fazendo a troca. Isso, no entanto, adiciona uma complexidade de tempo quadrática O(n^2) extra pois, para cada troca, precisaríamos "caminhar" ao menos por metade da lista, toda vez.
Ao "inverter" a orientação do ponto médio da lista em diante (1->2->3<-4<-5), isso reduz a complexidade de tempo para O(n), já que "andamos" pela lista à medida que fazemos as trocas.
É possível fazer uma solução ainda mais eficiente, mas julgo que essa mantém um custo benefício bom de eficiência enquanto permanece razoavelmente simples de explicar.
Antes de ir embora...
Espero que essa explicação simples tenha te ajudado a entender! Se você gosta do meu conteúdo, me ajuda a produzir cada vez mais enviando uma contribuição no pix : universodiscretopix@gmail.com.
Não deixe de visitar o youtube.com/universodiscreto para ver os conteúdos que tenho produzido em vídeo. Para saber tudo que produzo na internet, acesse linktr.ee/universodiscreto. Muito obrigado!