Sort List
Você recebe uma lista simplesmente encadeada armazenada em dois arrays de mesmo tamanho. O nó i contém o valor values[i] e aponta para o nó next[i], -1 encerra a lista, e a cabeça é o nó 0. Os nós não estão armazenados na ordem da lista, e os arrays também podem conter nós restantes que nunca são alcançados ao percorrer a partir do nó 0. Eles não fazem parte da lista, mesmo quando seus links apontam para dentro dela.
Ordene a lista em ordem não decrescente de valor e retorne os valores dos seus nós nessa ordem.
Função
- nextinteger-array
- o índice do nó ao qual cada nó está ligado, ou -1 para o último nó
- valuesinteger-array
- o valor armazenado por cada nó
- Retornainteger-array
- os valores dos nós da lista, do menor para o maior
Restrições
1 ≤ n ≤ 4000, ondené o comprimento denexte devalues.-1000 ≤ values[i] ≤ 1000- Cada
next[i]é-1ou um índice de nó de0an-1. - Começando no nó
0, a lista chega a-1sem visitar um nó duas vezes. - Nós que a travessia a partir do nó
0não alcança não fazem parte da lista. Suas entradasnextpodem apontar para qualquer lugar.
Exemplos
- Entrada
- next = [3, -1, 4, 2, 1]values = [4, 1, 3, 2, 5]
- Saída
- [1, 2, 3, 4, 5]
- Explicação
- O percurso a partir do nó
0visita os nós0, 3, 2, 4, 1, então a lista fica4, 2, 3, 5, 1. Ordenada, ela fica1, 2, 3, 4, 5.
- Entrada
- next = [2, 0, -1, -1]values = [6, 9, -2, 5]
- Saída
- [-2, 6]
- Explicação
- A lista é
0 → 2, que corresponde a6, -2. Os nós1e3nunca são alcançados a partir da cabeça, então seus valores9e5ficam de fora, embora o nó1esteja ligado ao nó0.
- Entrada
- next = [1, 2, 3, -1]values = [3, -1, 3, -1]
- Saída
- [-1, -1, 3, 3]
- Explicação
- A lista contém
3, -1, 3, -1. Valores iguais permanecem na resposta tantas vezes quantas aparecem:-1, -1, 3, 3.
Para ir além
Você consegue ordenar religando os nós em O(n log n) de tempo, sem copiar os valores para fora?
Dicas
Abra uma de cada vez. Cada uma revela um pouco mais.
Quais algoritmos de ordenação precisam saltar para uma posição arbitrária e quais apenas percorrem a entrada sempre para a frente? Uma lista encadeada é adequada para o segundo tipo.
Mesclar duas listas ordenadas em uma só não exige memória extra: você religará os nós, sempre escolhendo o menor dos dois valores no início. Se pudesse dividir a lista em duas metades ordenadas, uma mesclagem concluiria o trabalho.
Encontre o meio usando um ponteiro lento e um rápido e corte a lista nesse ponto. Ordene cada metade da mesma forma, parando em um único nó, que já está ordenado. Em seguida, mescle as duas metades ordenadas e retorne o novo início.
Solução
Quicksort e heapsort dependem de acesso aleatório, e uma lista simplesmente encadeada só avança. A ordenação por intercalação é adequada: dividir uma lista ao meio e intercalar duas listas ordenadas são operações que avançam, então ela ordena os próprios links em O(n log n). Aqui, n é o tamanho dos arrays.
Copie os valores para um array e ordene-o
Intuição
A lista é o que o percurso node = next[node] visita, do nó 0 até -1. Reúna esses valores em um novo array, ordene-o com a função de ordenação integrada e retorne-o. Você não pode ordenar values diretamente: no segundo exemplo, ele contém 9 e 5, que não estão na lista.
O percurso é O(n) e a ordenação é O(n log n), com O(n) de memória extra. A lista em si nunca é alterada, e é por isso que os entrevistadores perguntam pela próxima abordagem.
Algoritmo
- Comece com um array vazio e
node = 0. - Enquanto
nodenão for-1, adicionevalues[node]e avance paranext[node]. - Ordene o array em ordem crescente e retorne-o.
def sortList(next, values):
# Collect the values of the nodes on the list, then sort them.
on_list = []
node = 0
while node != -1:
on_list.append(values[node])
node = next[node]
on_list.sort()
return on_listOrdenação por intercalação nas listas encadeadas
Intuição
Um ponteiro lento que avança um nó e um ponteiro rápido que avança dois encontram o meio em uma única passagem. Para mesclar duas listas ordenadas, basta usar os nós iniciais: escolha o menor e avance para o próximo. Nenhuma das etapas precisa de um segundo array.
No primeiro exemplo, slow para no 3, e cortar seu link divide 4, 2, 3, 5, 1 em 4, 2, 3 e 5, 1. Essas listas são ordenadas como 2, 3, 4 e 1, 5, e a mesclagem pega 1, 2, 3, 4 e, em seguida, vincula o 5 restante.
Cada nível de divisão percorre cada nó um número constante de vezes, e há cerca de log n níveis, então o tempo é O(n log n). A única memória extra é a pilha de recursão, com cerca de 12 chamadas de profundidade para 4000 nós.
Algoritmo
- Se a lista tiver um nó (
next[head] == -1), retornehead. - Comece com
slow = headefast = next[head]; avanceslowum elo efastdois enquantofastenext[fast]não forem-1. - Defina
second = next[slow]e corte comnext[slow] = -1. - Ordene recursivamente as duas metades. Mescle-as: ligue o menor nó da frente após
tailaté que uma das metades fique vazia; então, ligue o restante da outra. - Percorra a lista a partir da cabeça retornada e colete os valores.
def sortList(next, values):
def merge(a, b):
# Splice two sorted lists into one; on a tie the node from a goes first.
head = tail = -1
while a != -1 and b != -1:
if values[b] < values[a]:
node, b = b, next[b]
else:
node, a = a, next[a]
if tail == -1:
head = node
else:
next[tail] = node
tail = node
next[tail] = a if a != -1 else b # attach whatever is left
return head
def sort(head):
if next[head] == -1: # one node is already sorted
return head
# slow stops on the last node of the first half
slow, fast = head, next[head]
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
return merge(sort(head), sort(second))
result = []
node = sort(0)
while node != -1:
result.append(values[node])
node = next[node]
return result
Armadilhas e casos extremos
- Ordenar o array
valuesinteiro. No segundo exemplo, isso inclui9e5, que não estão na lista. - Começar
fastna cabeça. Com dois nós,slowentão chega ao segundo nó, o corte deixa a segunda metade vazia e a recursão nunca diminui. - Esquecer o corte
next[slow] = -1. A primeira metade então continua pela segunda, e as duas chamadas ordenam listas sobrepostas. - Descartar o restante de uma metade quando a outra se esgota. Esses nós desaparecem do resultado.
- Em Lua e R, os arrays começam em 1: mantenha os índices dos nós baseados em 0 e leia
next[node + 1]. A versão em R copia o array de links uma vez, então usa memória extra O(n).
Perguntas frequentes3
Qual é a melhor maneira de ordenar uma lista encadeada?
Ordenação por intercalação. Dividir pelo meio, ordenar as duas metades e intercalá-las percorre a lista inteira para a frente, a única direção que uma lista simplesmente encadeada suporta. Ela é executada em O(n log n) e religa os nós existentes.
Por que o merge sort é preferido ao quicksort para listas encadeadas?
O Quicksort pode particionar uma lista religando os elementos, mas um bom pivô precisa de acesso aleatório, e escolher o primeiro elemento como pivô faz com que uma lista ordenada tenha custo O(n²). O Merge sort sempre divide ao meio, então permanece em O(n log n) para qualquer entrada.
Você consegue ordenar uma lista encadeada em tempo O(n log n) e com memória O(1)?
Sim, com o merge sort bottom-up. Ele mescla sequências vizinhas de comprimento 1, depois 2, depois 4, até que uma sequência cubra a lista. Há log n passagens lineares, e a única memória utilizada são alguns índices de nós.
Problemas parecidos
Problemas que usam as mesmas ideias. Resolver dois ou três é o que fixa um padrão.
def sortList(next, values):
# Escreva o código aquiTeste #1
Teste #2
Teste #3
Argumentos
next = [3, -1, 4, 2, 1] values = [4, 1, 3, 2, 5]
Saída Esperada
[1, 2, 3, 4, 5]