Mesclar cadeias ordenadas
A missão
Problema
Duas listas simplesmente encadeadas já estão, cada uma, em ordem não decrescente. Junte-as em uma única lista ordenada religando os nós existentes, em vez de criar nós novos. Retorne o head da lista mesclada, que fica vazia quando as duas entradas estão vazias.
Exemplos
Input: a = 1 -> 4 -> 6, b = 2 -> 3
Output: 1 -> 2 -> 3 -> 4 -> 6
Input: a = empty, b = 7
Output: 7
Por quê: edge case: um dos lados acaba antes de o loop começar
Input: a = empty, b = empty
Output: empty
Por quê: edge case: não há nada para mesclar
Dicas
0 / 3
A cada momento, só dois candidatos podem vir em seguida: a frente atual de cada cadeia. O resto das duas cadeias é irrelevante até que uma delas seja consumida.
Montar uma lista pela frente é desajeitado, então guarde um ponteiro para o último nó do resultado e sempre ligue os nós atrás dele. Um nó inicial descartável elimina o caso especial da primeira ligação.
Compare repetidamente os dois nós da frente, desligue o menor e pendure-o no tail do resultado. Quando uma cadeia esvaziar, ligue a cadeia restante inteira de uma só vez, porque ela já está ordenada.
- Tempo-alvo
- O(n + m)
- Espaço-alvo
- O(1)
Restrições
- both lists are sorted in non-decreasing order
- either list may be empty
Solução
As duas cadeias são consumidas frente a frente, sempre pegando o menor head e anexando-o ao tail do resultado. Um nó dummy inicial faz com que a primeira anexação não precise de tratamento especial, e o head real é simplesmente o nó depois dele. Quando uma cadeia se esgota, a outra já está ordenada, então o restante é ligado de uma vez, em vez de nó por nó. O tempo é O(n + m) e o espaço é O(1), já que só os ponteiros mudam.
class Node:
def __init__(self, val, nxt=None): self.val, self.next = val, nxt
def build(v): return Node(v[0], build(v[1:])) if v else None # list -> chain
def dump(h): return [h.val] + dump(h.next) if h else [] # chain -> list
def merge_sorted(a, b):
dummy = tail = Node(0) # starter node removes the empty-result case
while a and b:
if a.val <= b.val: tail.next, a = a, a.next
else: tail.next, b = b, b.next
tail = tail.next # the attached node is the new tail
tail.next = a or b # the leftover chain is already sorted
return dummy.next
print(dump(merge_sorted(build([1, 4, 6]), build([2, 3])))) # -> [1, 2, 3, 4, 6]
print(dump(merge_sorted(build([]), build([7])))) # -> [7]
print(dump(merge_sorted(build([]), build([])))) # -> []Travou na ideia, e não no código? Merge Two Sorted Lists explica isso.