24 de Março
Mesclar duas listas ordenadas
Como perceber que as listas já estao ordenadas e que a comparação certa sempre acontece nas cabecas.
Lista Encadeada Iniciante 18 min TypeScript
Dadas as cabecas de duas listas encadeadas ordenadas list1 e list2, faca o merge em uma unica lista ordenada e retorne sua cabeca.
Exemplo:
Input: 1 -> 2 -> 4, 1 -> 3 -> 4
Output: 1 -> 1 -> 2 -> 3 -> 4 -> 4
O que perceber antes de codar
- As duas listas já chegam ordenadas.
- A cada passo, a escolha certa esta entre as duas cabecas atuais.
- Quando uma lista acaba, o resto da outra já pode ser conectado inteiro.
Erros comuns
- esquecer de conectar o restante quando uma das listas termina
- avancar o ponteiro errado depois de escolher um no
Passo 1 — Entender qual informação já veio pronta
O problema não te entrega duas listas quaisquer.
Ele te entrega duas listas ordenadas.
Se você ignora isso, perde a melhor pista do enunciado.
Passo 2 — Escrever uma versão inicial correta
Uma versão inicial valida e juntar todos os valores, ordenar e reconstruir:
export function mergeTwoLists(list1, list2) {
const values = []
let left = list1
let right = list2
while (left) {
values.push(left.val)
left = left.next
}
while (right) {
values.push(right.val)
right = right.next
}
values.sort((a, b) => a - b)
const dummy = { val: 0, next: null }
let tail = dummy
for (const value of values) {
tail.next = { val: value, next: null }
tail = tail.next
}
return dummy.next
}
Funciona. Mas a ordenação extra não precisava existir.
Passo 3 — Perguntar onde esta o menor próximo valor
Como as listas já estao ordenadas, o menor valor que falta entrar só pode estar em um destes dois lugares:
- cabeca atual de
list1 - cabeca atual de
list2
Não precisa procurar no resto.
Passo 4 — Costurar a resposta enquanto anda
Use:
- um no sentinela (
dummy) para simplificar a cabeca da resposta - um
tailpara apontar onde anexar o próximo no
Compare as cabecas, conecte o menor e avance só a lista usada.
O editor interativo precisa de JavaScript. Voce ainda pode ler o desafio e copiar o codigo inicial abaixo.
Codigo inicial
export function mergeTwoLists(list1, list2) {
// list nodes are objects like { val: number, next: ... } or null
// sua solução aqui
return null
}
Ainda não resolveu?
Ver a solução agora pode reduzir o aprendizado. Vale a pena tentar mais um pouco.
Abrir a solucao de referencia
Sem JavaScript, a solucao de referencia aparece inline em vez de um dialogo.
Solução
Complexidade final
Tempo: O(n + m)
Espaço: O(1)
Solução 1 — Juntar, ordenar e reconstruir
Serve como versão inicial, mas desperdiça a ordenação já dada.
export function mergeTwoLists(list1, list2) {
const values = []
let left = list1
let right = list2
while (left) {
values.push(left.val)
left = left.next
}
while (right) {
values.push(right.val)
right = right.next
}
values.sort((a, b) => a - b)
const dummy = { val: 0, next: null }
let tail = dummy
for (const value of values) {
tail.next = { val: value, next: null }
tail = tail.next
}
return dummy.next
}Solução 2 — Merge linear com ponteiros e no sentinela
Agora a solução usa o fato de que as listas já estao ordenadas.
export function mergeTwoLists(list1, list2) {
const dummy = { val: 0, next: null }
let tail = dummy
let left = list1
let right = list2
while (left && right) {
if (left.val <= right.val) {
tail.next = left
left = left.next
} else {
tail.next = right
right = right.next
}
tail = tail.next
}
tail.next = left ?? right
return dummy.next
}Quando uma lista termina, o resto da outra já esta na ordem certa.
O que dizer na entrevista
Uma explicação curta e boa seria:
A versão inicial poderia juntar tudo e ordenar de novo, mas isso ignora que as duas listas já estao ordenadas. Entao eu comparo só as cabecas atuais, conecto o menor no final da resposta e avanço a lista correspondente. Isso vira um merge linear em
O(n + m).
Isso mostra que você:
- aproveitou a estrutura do input
- entendeu o padrão de merge ordenado
- explicou a resposta sem adicionar trabalho desnecessario
Quando esse padrão aparece de novo
Esse padrão reaparece quando você precisa:
- combinar sequencias ordenadas
- escolher sempre entre duas fronteiras
- construir resposta incrementalmente
- usar no sentinela para simplificar ponteiros
O ponto não e decorar esse problema.
O ponto e reconhecer quando a ordenação já veio pronta e só falta costurar.