Merge Two Sorted Lists

Q: Qual è la complessità temporale dell'unione di due liste ordinate?

È O(L1 + L2) : ogni confronto colloca un nodo e nessun nodo viene collocato due volte. Con oggetti nodo, la fusione richiede O(1) di memoria aggiuntiva, poiché modifica solo i collegamenti. Con gli array usati qui, l’array di collegamenti condiviso occupa O(L1 + L2) di memoria.

FacileLista concatenata Due puntatori

+10

Ricevi due liste concatenate singolarmente, ciascuna memorizzata in due array della stessa lunghezza. Nella prima lista, il nodo i contiene il valore values1[i] e punta al nodo next1[i]. La seconda lista funziona allo stesso modo con next2 e values2. In entrambe le liste, -1 indica la fine della lista e la testa è il nodo 0. I nodi non sono memorizzati nell'ordine della lista, quindi segui i collegamenti.

Ciascuna lista è ordinata in modo non decrescente lungo i collegamenti. Unisci le due liste in un'unica lista ordinata e restituisci i valori nell'ordine corretto.

Funzione

mergeTwoLists(next1: integer-array, values1: integer-array, next2: integer-array, values2: integer-array) → integer-array

next1integer-array: l'indice del nodo a cui è collegato ciascun nodo della prima lista, oppure -1 per il suo ultimo nodo
values1integer-array: il valore contenuto in ciascun nodo della prima lista
next2integer-array: l'indice del nodo a cui è collegato ciascun nodo della seconda lista, oppure -1 per il suo ultimo nodo
values2integer-array: il valore contenuto in ciascun nodo della seconda lista
Restituisceinteger-array: i valori della lista unita, nell’ordine

Vincoli

1 ≤ L1 ≤ 2000, dove L1 è la lunghezza di next1 e di values1.
1 ≤ L2 ≤ 2000, dove L2 è la lunghezza di next2 e di values2.
-1000 ≤ values1[i], values2[j] ≤ 1000
Ogni elemento di next1 è -1 oppure l'indice di un nodo della prima lista, e ogni elemento di next2 è -1 oppure l'indice di un nodo della seconda lista.
Partendo dal nodo 0, ogni lista visita ciascuno dei suoi nodi esattamente una volta e poi raggiunge -1. Non c'è alcun ciclo.
Lungo i suoi collegamenti, ogni lista è ordinata in ordine non decrescente.

Esempi

Input: next1 = [2, -1, 1]values1 = [1, 6, 4]next2 = [3, 2, -1, 1]values2 = [2, 7, 9, 3]
Output: [1, 2, 3, 4, 6, 7, 9]
Spiegazione: Seguendo i collegamenti, la prima lista visita i nodi 0, 2, 1 e legge 1, 4, 6; la seconda legge 2, 3, 7, 9. Prendendo ogni volta il valore più piccolo in testa si ottiene 1, 2, 3, 4, 6, 7, 9.

Input: next1 = [2, -1, 1]values1 = [-3, 5, 0]next2 = [-1]values2 = [0]
Output: [-3, 0, 0, 5]
Spiegazione: La prima lista contiene -3, 0, 5 e la seconda è il singolo valore 0. Entrambi gli 0 restano nel risultato, quindi contiene quattro valori.

Input: next1 = [1, -1]values1 = [8, 10]next2 = [2, -1, 1]values2 = [1, 3, 2]
Output: [1, 2, 3, 8, 10]
Spiegazione: La seconda lista legge 1, 2, 3, tutti più piccoli di 8 che dà inizio alla prima lista. Prima viene l’intera seconda lista, poi 8, 10.

Per approfondire

Riesci a unire k liste ordinate in tempo O(N log k), dove N è il numero totale di nodi?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Entrambi gli elenchi sono ordinati, quindi il valore più piccolo rimasto è sempre in testa a uno dei due. Confronta i primi elementi, collega quello più piccolo al risultato e avanza in quell’elenco. Ordinare tutti i N = L1 + L2 valori funziona ugualmente, ma ignora quest’ordine e ha un costo di O(N log N).

Inserisci ogni valore in un array e ordinali

Intuizione

La lista unita è la versione ordinata di tutti i valori N, quindi copia entrambi gli array di valori in uno solo e ordinalo. L’ordine dei nodi all’interno degli array non importa, perché l’ordinamento colloca ogni valore. Con N ≤ 4000 è abbastanza veloce, ma un ordinamento richiede O(N log N) confronti, mentre una fusione ne richiede al massimo N-1, e non tocca mai un collegamento, che è l’abilità verificata da questo problema.

Algoritmo

Copia values1 e values2 in un unico array.
Ordina l’array in ordine non decrescente.
Restituiscilo.

def mergeTwoLists(next1, values1, next2, values2):
    # Sorting puts every value in its place without following a single link.
    return sorted(values1 + values2)

Collega i nodi dopo una testa fittizia

Intuizione

Un puntatore qui è un indice di nodo. Per collegare i nodi di entrambe le liste in un'unica catena, assegna loro una numerazione: il nodo j della lista 2 diventa il nodo L1+j, con i suoi collegamenti spostati allo stesso modo. Un nodo fittizio, numerato L1+L2, si trova davanti al risultato.

Mantieni a e b sul primo nodo non ancora utilizzato di ciascuna lista e tail alla fine della catena unita. A ogni passaggio, collega tail al nodo iniziale più piccolo e sposta in avanti quel puntatore e tail. Quando una lista si esaurisce, il resto dell'altra è già ordinato e collegato, quindi basta un'assegnazione per aggiungerlo. Nel primo esempio, la lista 2 diventa i nodi da 3 a 6. Dopo i nodi 0, 3, 6, 2, 1, la lista 1 è vuota e link[tail] = 4 aggiunge 7, 9.

Ogni nodo viene collegato al massimo una volta: tempo O(N). L'array condiviso dei collegamenti richiede O(N) di memoria, mentre gli oggetti nodo non ne richiederebbero.

Algoritmo

Crea un unico array di collegamenti: next1, poi next2 spostato di L1 (lascia invariato -1), poi -1 per il nodo fittizio L1+L2. Crea i valori corrispondenti.
Imposta a = 0, b = L1 e tail sul nodo fittizio.
Finché né a né b è -1, collega tail al più piccolo (in caso di parità, a), avanza quel puntatore e sposta tail su di esso.
Collega tail a quello tra a e b che non è -1.
Procedi da link[dummy] fino a -1 e raccogli i valori.

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

Trappole e casi limite

Unire gli array in ordine di indice. I nodi sono memorizzati in ordine casuale, quindi values1 non è ordinato: nel primo esempio è [1, 6, 4]. Solo il percorso a partire dal nodo 0 è ordinato.
Dimenticare gli elementi rimanenti. Quando una lista termina, il ciclo si interrompe e scartare il resto dell’altra lista fa perdere i valori più grandi: 7, 9 nel primo esempio.
Avanzare il puntatore sbagliato, o entrambi. Avanza solo la lista da cui hai preso il nodo.
Confondere le due numerazioni. Il nodo 2 della lista 2 non è il nodo 2 della lista 1. Trasla gli indici e i collegamenti della lista 2 di L1 e lascia -1 così com’è.

Domande frequenti3

Qual è la complessità temporale dell'unione di due liste ordinate?

È O(L1 + L2): ogni confronto colloca un nodo e nessun nodo viene collocato due volte. Con oggetti nodo, la fusione richiede O(1) di memoria aggiuntiva, poiché modifica solo i collegamenti. Con gli array usati qui, l’array di collegamenti condiviso occupa O(L1 + L2) di memoria.

Perché usare un nodo fittizio quando si fondono liste concatenate?

Senza di esso, il primo nodo del risultato richiede codice separato, perché non c'è ancora una coda a cui collegarlo dopo. Il nodo fittizio è una testa segnaposto, quindi il primo nodo viene collegato nello stesso modo di tutti gli altri. Alla fine restituisci il nodo successivo del nodo fittizio e il segnaposto scompare.

Conviene unire ricorsivamente o iterativamente due liste ordinate?

La versione ricorsiva è breve: l'elemento iniziale più piccolo punta alla fusione di tutto il resto. Ma usa un frame dello stack per nodo, quindi una lista di qualche migliaio di nodi può causare un overflow dello stack in alcuni linguaggi. Il ciclo iterativo con un puntatore alla coda svolge lo stesso lavoro usando uno spazio costante nello stack.

def mergeTwoLists(next1, values1, next2, values2):
    # Scrivi il codice qui

Test #1

Test #2

Test #3

Argomenti

next1 = [2, -1, 1]
values1 = [1, 6, 4]
next2 = [3, 2, -1, 1]
values2 = [2, 7, 9, 3]

Output atteso

[1, 2, 3, 4, 6, 7, 9]