Merge Two Sorted Lists
Você recebe duas listas simplesmente encadeadas, cada uma armazenada em dois arrays de mesmo tamanho. Na primeira lista, o nó i contém o valor values1[i] e aponta para o nó next1[i]. A segunda lista funciona da mesma forma, com next2 e values2. Em ambas as listas, -1 indica o fim da lista, e a cabeça é o nó 0. Os nós não estão armazenados na ordem da lista, então siga os links.
Cada lista está ordenada em ordem não decrescente ao longo dos links. Mescle as duas em uma única lista ordenada e retorne seus valores em ordem.
Função
- next1integer-array
- o índice do nó ao qual cada nó da primeira lista está ligado, ou -1 para o último nó
- values1integer-array
- o valor armazenado por cada nó da primeira lista
- next2integer-array
- o índice do nó ao qual cada nó da segunda lista está ligado, ou -1 para seu último nó
- values2integer-array
- o valor armazenado por cada nó da segunda lista
- Retornainteger-array
- os valores da lista mesclada, em ordem
Restrições
1 ≤ L1 ≤ 2000, em queL1é o comprimento denext1e devalues1.1 ≤ L2 ≤ 2000, em queL2é o comprimento denext2e devalues2.-1000 ≤ values1[i], values2[j] ≤ 1000- Cada entrada de
next1é-1ou um índice de nó da primeira lista, e cada entrada denext2é-1ou um índice de nó da segunda lista. - Começando no nó
0, cada lista visita cada um de seus nós exatamente uma vez e, em seguida, chega a-1. Não há ciclo. - Seguindo seus links, cada lista está ordenada em ordem não decrescente.
Exemplos
- Entrada
- next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
- Saída
- [1, 2, 3, 4, 6, 7, 9]
- Explicação
- Seguindo os links, a primeira lista visita os nós
0, 2, 1e lê1, 4, 6; a segunda lê2, 3, 7, 9. Pegando o menor elemento da frente a cada vez, obtemos1, 2, 3, 4, 6, 7, 9.
- Entrada
- next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
- Saída
- [-3, 0, 0, 5]
- Explicação
- A primeira lista contém
-3, 0, 5e a segunda é o valor único0. Ambos os0permanecem no resultado, que tem quatro valores.
- Entrada
- next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
- Saída
- [1, 2, 3, 8, 10]
- Explicação
- A segunda lista é
1, 2, 3, todos menores que o8que inicia a primeira lista. A segunda lista inteira vem primeiro, depois8, 10.
Para ir além
Você consegue mesclar k listas ordenadas em O(N log k) tempo, em que N é o número total de nós?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
As duas listas já estão ordenadas. Quais são os dois valores que são os únicos candidatos ao menor valor da lista mesclada?
Mantenha um ponteiro no primeiro nó não utilizado de cada lista. O menor dos dois valores vem a seguir, e somente esse ponteiro avança. Quando uma das listas acabar, tudo o que restar na outra já estará em ordem.
Numere os nós da segunda lista após os da primeira, para que um único array de links cubra ambas, e adicione um nó fictício no início. Mantenha um
tailno último nó da lista mesclada, aponte seu link para o menor nó da frente e avance. No final, percorra a lista a partir do nó fictício e colete os valores.
Solução
Ambas as listas estão ordenadas, então o menor valor restante está sempre no início de uma delas. Compare os dois primeiros elementos, vincule o menor deles ao resultado e avance nessa lista. Ordenar todos os N = L1 + L2 valores também funciona, mas ignora essa ordem e custa O(N log N).
Coloque todos os valores em um único array e ordene-o
Intuição
A lista mesclada é a versão ordenada de todos os valores N, então copie os dois arrays de valores em um só e ordene-o. A ordem dos nós dentro dos arrays não importa, porque a ordenação posiciona todos os valores. Com N ≤ 4000, isso é rápido o suficiente, mas uma ordenação custa O(N log N) comparações, enquanto uma mesclagem precisa de no máximo N-1 e nunca mexe em um link — justamente a habilidade que este problema avalia.
Algoritmo
- Copie
values1evalues2em um único array. - Classifique o array em ordem não decrescente.
- Retorne-o.
def mergeTwoLists(next1, values1, next2, values2):
# Sorting puts every value in its place without following a single link.
return sorted(values1 + values2)Intercale os nós atrás de uma cabeça fictícia
Intuição
Um ponteiro aqui é um índice de nó. Para conectar os nós das duas listas em uma única cadeia, atribua-lhes uma numeração: o nó j da lista 2 passa a ser o nó L1+j, com seus links deslocados da mesma maneira. Um nó fictício, de número L1+L2, fica à frente do resultado.
Mantenha a e b no primeiro nó não utilizado de cada lista e tail no final da cadeia mesclada. A cada etapa, conecte tail ao menor dos nós iniciais e avance esse ponteiro e tail. Quando uma lista acabar, o restante da outra já estará ordenado e conectado, então uma atribuição o anexa. No primeiro exemplo, a lista 2 passa a ser os nós 3 a 6. Depois dos nós 0, 3, 6, 2, 1, a lista 1 está vazia e link[tail] = 4 anexa 7, 9.
Cada nó é conectado no máximo uma vez: tempo O(N). O array de links compartilhado ocupa O(N) de memória, enquanto objetos de nó não precisariam de nenhuma.
Algoritmo
- Monte um único array de ligações:
next1, depoisnext2deslocado porL1(deixe-1como está) e, em seguida,-1para o elemento fictícioL1+L2. Monte os valores correspondentes. - Defina
a = 0,b = L1etailcomo o elemento fictício. - Enquanto nem
anembfor-1, liguetailao menor (em caso de empate,a), avance esse ponteiro e movatailpara ele. - Ligue
tailàquele entreaebque não for-1. - Percorra a partir de
link[dummy]até-1e colete os valores.
def mergeTwoLists(next1, values1, next2, values2):
n1 = len(next1)
n2 = len(next2)
# One node space: list 2's node j becomes node n1 + j, and node n1 + n2 is a
# dummy that sits in front of the merged list.
link = list(next1) + [j + n1 if j != -1 else -1 for j in next2] + [-1]
value = list(values1) + list(values2)
dummy = n1 + n2
tail = dummy # the last node of the merged list so far
a = 0 # the first unused node of list 1
b = n1 # the first unused node of list 2
while a != -1 and b != -1:
if value[a] <= value[b]:
link[tail] = a # splice a in after the tail
a = link[a]
else:
link[tail] = b # splice b in after the tail
b = link[b]
tail = link[tail]
# One list ran out. The rest of the other one is sorted and linked already.
link[tail] = a if a != -1 else b
merged = []
node = link[dummy]
while node != -1:
merged.append(value[node])
node = link[node]
return merged
Armadilhas e casos extremos
- Mesclar os arrays em ordem de índice. Os nós são armazenados embaralhados, então
values1não está ordenado: no primeiro exemplo, ele é[1, 6, 4]. Apenas o percurso a partir do nó0está ordenado. - Esquecer os elementos restantes. Quando uma lista acaba, o loop para, e descartar o restante da outra lista faz com que os maiores valores sejam perdidos:
7, 9no primeiro exemplo. - Avançar o ponteiro errado, ou ambos. Apenas a lista cujo nó foi escolhido avança.
- Misturar as duas numerações. O nó
2da lista 2 não é o nó2da lista 1. Desloque os índices e links da lista 2 porL1e deixe-1como está.
Perguntas frequentes3
Qual é a complexidade de tempo para mesclar duas listas ordenadas?
É O(L1 + L2): cada comparação posiciona um nó, e nenhum nó é posicionado duas vezes. Com objetos de nó, a intercalação requer O(1) de memória extra, pois apenas altera os links. Com os arrays usados aqui, o array de links compartilhado custa O(L1 + L2) de memória.
Por que usar um nó fictício ao mesclar listas encadeadas?
Sem ele, o primeiro nó do resultado precisa de um código separado, porque ainda não há uma cauda para vinculá-lo depois. O nó fictício é uma cabeça substituta, então o primeiro nó é vinculado da mesma forma que todos os outros. No final, você retorna o próximo nó do nó fictício e o espaço reservado desaparece.
Você deve mesclar duas listas ordenadas recursivamente ou iterativamente?
A versão recursiva é curta: a cabeça menor aponta para a mesclagem de todo o restante. Mas ela usa um quadro de pilha por nó, então uma lista com alguns milhares de nós pode causar estouro de pilha em algumas linguagens. O laço iterativo com um ponteiro para a cauda faz o mesmo trabalho usando espaço de pilha constante.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def mergeTwoLists(next1, values1, next2, values2):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
next1 = [2, -1, 1] values1 = [1, 6, 4] next2 = [3, 2, -1, 1] values2 = [2, 7, 9, 3]
Saída Esperada
[1, 2, 3, 4, 6, 7, 9]