Reorder List
Ti viene fornita una lista concatenata semplice memorizzata in due array della stessa lunghezza. Il nodo i contiene il valore values[i] ed è collegato al nodo next[i]; -1 termina la lista e la testa è il nodo 0. I nodi non sono memorizzati nell'ordine della lista, quindi segui i collegamenti.
Chiama i nodi nell'ordine della lista L0, L1, ..., Lk. Riordina la lista in modo che segua l'ordine L0, Lk, L1, Lk-1, L2, Lk-2, ...: prima il primo nodo, poi l'ultimo, poi il secondo, poi il penultimo e così via. Restituisci i valori in questo nuovo ordine.
Funzione
- nextinteger-array
- l'indice del nodo a cui è collegato ciascun nodo, oppure -1 per l'ultimo nodo
- valuesinteger-array
- il valore contenuto in ciascun nodo
- Restituisceinteger-array
- i valori nell'ordine dell'elenco riordinato
Vincoli
1 ≤ n ≤ 4000, dovenè la lunghezza dinexte divalues.-1000 ≤ values[i] ≤ 1000- Ogni
next[i]è-1oppure un indice di nodo da0an-1. - Partendo dal nodo
0, la lista visita ogni nodo esattamente una volta e poi raggiunge-1. Non c'è alcun ciclo.
Esempi
- Input
- next = [3, 4, -1, 1, 2]values = [1, 3, 5, 2, 4]
- Output
- [1, 5, 2, 4, 3]
- Spiegazione
- Seguendo i collegamenti dal nodo
0, la lista si legge1, 2, 3, 4, 5. Primo, ultimo, secondo e penultimo danno1, 5, 2, 4, e il valore centrale3viene per ultimo.
- Input
- next = [2, 3, 1, -1]values = [10, 30, 20, 40]
- Output
- [10, 40, 20, 30]
- Spiegazione
- La lista visita i nodi
0, 2, 1, 3e legge10, 20, 30, 40. Il primo e l’ultimo danno10, 40, poi la coppia interna dà20, 30.
- Input
- next = [-1]values = [7]
- Output
- [7]
- Spiegazione
- Una lista con un solo nodo non ha nulla da spostare, quindi la risposta è
[7].
Per approfondire
Riesci a riordinare i collegamenti stessi usando memoria aggiuntiva O(1)?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Scrivi l'ordine di destinazione per
1, 2, 3, 4, 5, 6. Quali nodi provengono dalla metà anteriore della lista e in quale ordine compaiono i nodi della metà posteriore?La metà posteriore appare al contrario:
6, 5, 4. Se la metà posteriore fosse invertita, la risposta sarebbe costituita da due liste unite prendendo un nodo da ciascuna a turno.Trova il centro con un puntatore lento che avanza di un collegamento e un puntatore veloce che ne avanza due. Dividi la lista dopo il centro, inverti la seconda parte capovolgendone i collegamenti, quindi intreccia le due parti insieme, nodo per nodo.
Soluzione
Il nuovo ordine alterna la parte anteriore e quella posteriore, ma una lista semplicemente concatenata procede solo in avanti. Suddividi il lavoro in tre operazioni standard sulle liste: trova il punto centrale con puntatori lento e veloce, inverti la metà posteriore e intreccia le due metà un nodo alla volta.
Muovi la coda in avanti, un nodo alla volta
Intuizione
Qui un puntatore è un indice di nodo e avanzare significa node = next[node]. Dopo il primo nodo viene l'ultimo, quindi sgancia l'ultimo nodo e inseriscilo dopo quello corrente, poi ripeti due nodi più avanti. Per 1, 2, 3, 4, 5 si ottiene 1, 5, 2, 3, 4, poi 1, 5, 2, 4, 3. Fermati quando dopo quello corrente rimangono meno di due nodi.
Per trovare il nodo che precede l'ultimo bisogna percorrere la lista fino alla fine a ogni iterazione. I percorsi si accorciano di due nodi a ogni iterazione, per un totale di circa n²/4 spostamenti: quattro milioni per 4000 nodi.
Algoritmo
- Imposta
cur = 0. - Finché dopo
curseguono almeno due nodi, fai avanzarebeforedacurfinchénext[next[before]] == -1, cosìtail = next[before]è l’ultimo nodo. - Sgancialo con
next[before] = -1, poi inseriscilo:next[tail] = next[cur]enext[cur] = tail. - Sposta
cursunext[tail]e ripeti. - Parti dal nodo
0e raccogli i valori.
def reorderList(next, values):
cur = 0
# While at least two nodes follow cur, move the last node right after cur.
while next[cur] != -1 and next[next[cur]] != -1:
before = cur
while next[next[before]] != -1: # find the node before the tail
before = next[before]
tail = next[before]
next[before] = -1
next[tail] = next[cur]
next[cur] = tail
cur = next[tail]
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return resultCopia i valori e leggi da entrambe le estremità
Intuizione
Un array raggiunge il suo ultimo elemento in un solo passaggio. Copia i valori nell’ordine della lista, [1, 2, 3, 4, 5] nel primo esempio, poi leggi con lo dall’inizio e con hi dalla fine: prendi lo, prendi hi e sposta entrambi verso l’interno mentre lo < hi. Si ottiene 1, 5, 2, 4; con una lunghezza dispari, entrambi raggiungono l’elemento centrale 3, che va per ultimo.
La complessità è O(n) in termini di tempo e O(n) di memoria aggiuntiva, e i collegamenti non cambiano.
Algoritmo
- Percorri a partire dal nodo
0e aggiungi ogni valore ainOrder. - Imposta
lo = 0ehiall’ultimo indice. - Mentre
lo < hi, aggiungiinOrder[lo]einOrder[hi], poi incrementaloe decrementahi. - Se
lo == hi, aggiungi il valore centrale.
def reorderList(next, values):
# Write the values out in list order.
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
# Take from the front and the back in turn.
result = []
lo, hi = 0, len(in_order) - 1
while lo < hi:
result.append(in_order[lo])
result.append(in_order[hi])
lo += 1
hi -= 1
if lo == hi: # odd length: the middle value comes last
result.append(in_order[lo])
return resultTrova il centro, inverti la metà posteriore, intreccia
Intuizione
Per 1, 2, 3, 4, 5, 6 la risposta è 1, 6, 2, 5, 3, 4: la metà anteriore 1, 2, 3 in ordine, alternata con la metà posteriore 4, 5, 6 letta al contrario. Quindi taglia la lista a metà, inverti la metà posteriore e intrecciale.
slow avanza di un collegamento, mentre fast ne avanza di due, quindi slow si ferma sull'ultimo nodo della metà anteriore: il 3, sia con cinque che con sei nodi. Tagliando dopo di esso, la metà anteriore contiene il nodo in più quando la lunghezza è dispari, e quel nodo conclude la risposta. L'intreccio prende a turno un nodo da ciascuna metà finché la metà posteriore non si esaurisce.
Ogni nodo viene visitato un numero costante di volte, usando solo pochi indici di memoria. R copia il vettore dei collegamenti alla prima modifica, quindi in R la memoria è O(n).
Algoritmo
- Sposta
slowdi un collegamento efastdi due collegamenti mentrenext[fast]enext[next[fast]]non sono-1. - Imposta
second = next[slow], poinext[slow] = -1. - Inverti la lista che inizia da
second; la sua nuova testa èprev. - Intreccia: mentre
secondnon è-1, collegafirstasecondesecondal vecchionext[first], poi avanza entrambi. - Percorri a partire dal nodo
0e raccogli i valori.
def reorderList(next, values):
# 1. Find the middle: slow stops on the last node of the first half.
slow = fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
second = next[slow]
next[slow] = -1 # cut the list in two
# 2. Reverse the second half.
prev = -1
while second != -1:
after = next[second]
next[second] = prev
prev = second
second = after
# 3. Weave: one node from the front half, one from the reversed back half.
first, second = 0, prev
while second != -1:
first_after, second_after = next[first], next[second]
next[first] = second
next[second] = first_after
first, second = first_after, second_after
result = []
node = 0
while node != -1:
result.append(values[node])
node = next[node]
return result
Trappole e casi limite
- Non interrompere la lista a metà. Senza
next[slow] = -1, la metà anteriore continua a puntare alla metà posteriore e, dopo l'intreccio, la lista ricomincia da capo. - Sovrascrivere un collegamento prima di salvarlo. Nell'inversione e nell'intreccio, leggi prima
next[node]in una variabile, altrimenti il resto della lista va perso. - Continuare a intrecciare finché termina la metà anteriore. Con una lunghezza dispari, il ciclo viene eseguito un'altra volta con
seconda-1e leggenext[-1]. - Leggere l'ordine dell'array come l'ordine della lista. Nel primo esempio
valuesè[1, 3, 5, 2, 4], ma la lista si legge1, 2, 3, 4, 5. - In Lua e R gli array iniziano da 1. Mantieni gli indici dei nodi a base 0 e leggi
next[node + 1].
Domande frequenti3
Perché invertire la seconda metà della lista?
La risposta legge la metà posteriore dall'ultimo nodo al primo, mentre una lista collegata singolarmente procede solo in avanti. Invertire una volta la metà posteriore, in O(n), permette all'unione di scorrere entrambe le metà in avanti.
Qual è la complessità temporale di Reorder List?
Il metodo in-place viene eseguito in tempo O(n) con memoria aggiuntiva O(1): trovare il punto centrale, invertire e intrecciare richiedono ciascuna di visitare ogni nodo un numero costante di volte. Copiare i valori in un array richiede anch’esso tempo O(n), ma necessita di memoria O(n), mentre spostare la coda in avanti di un nodo alla volta richiede O(n²).
Dov'è il centro quando la lista ha un numero pari di nodi?
Ferma il puntatore lento sull’ultimo nodo della metà anteriore. Con sei nodi, le metà sono di tre e tre; con cinque, di tre e due. Il nodo in più determina quindi la risposta: è lì che l’ordine colloca il valore centrale.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def reorderList(next, values):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
next = [3, 4, -1, 1, 2] values = [1, 3, 5, 2, 4]
Output atteso
[1, 5, 2, 4, 3]