Pular para o conteúdo

Mesclar cadeias ordenadas

Fácil#two-pointers#dummy-node~20 min

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

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

Travou na ideia, e não no código? Merge Two Sorted Lists explica isso.

Python 3Ctrl+Enter executa