Reverse Linked List

Q: Come si inverte una lista concatenata sul posto?

Percorri la lista con due puntatori: prev inizializzato a niente e node inizializzato alla testa. Per ogni nodo, salva il nodo successivo, imposta il suo collegamento a prev , quindi sposta prev e node avanti di un passo. Quando node termina, prev è la testa della lista invertita.

Q: Qual è la complessità temporale e spaziale dell’inversione di una lista concatenata?

La versione iterativa visita ogni nodo una volta, tempo O(n) , e mantiene tre puntatori, spazio aggiuntivo O(1) . Copiare prima l’ordine in un array richiede anch’esso tempo O(n) , ma necessita di spazio aggiuntivo O(n) . Una versione ricorsiva usa O(n) di spazio per lo stack delle chiamate.

FacileLista concatenata

+10

Hai una lista concatenata singola memorizzata nell'array next: il nodo i punta 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.

Inverti la lista capovolgendo ogni collegamento, in modo che il vecchio ultimo nodo diventi la testa e il nodo 0 diventi l'ultimo nodo, collegato a -1. Restituisci l'array next aggiornato, che ha la stessa lunghezza dell'input.

Funzione

reverseList(next: integer-array) → integer-array

nextinteger-array: l'indice del nodo a cui è collegato ciascun nodo, oppure -1 per l'ultimo nodo
Restituisceinteger-array: l'array successivo della lista invertita

Vincoli

1 ≤ next.length ≤ 5000
Ogni next[i] è -1 oppure un indice di nodo da 0 a next.length-1.
Partendo dal nodo 0, la lista visita ogni nodo esattamente una volta e poi raggiunge -1. Non c'è alcun ciclo.

Esempi

Input: next = [1, 2, 3, -1]
Output: [-1, 0, 1, 2]
Spiegazione: La lista è 0 → 1 → 2 → 3. Invertita è 3 → 2 → 1 → 0, quindi il nodo 3 punta a 2, il nodo 2 a 1, il nodo 1 a 0 e il nodo 0 a -1.

Input: next = [2, -1, 3, 1]
Output: [-1, 3, 0, 2]
Spiegazione: La lista è 0 → 2 → 3 → 1 e, invertita, è 1 → 3 → 2 → 0. Scrivendo ogni nuovo collegamento all'indice del suo nodo si ottiene [-1, 3, 0, 2]. Invertendo l'array stesso si otterrebbe [1, 3, -1, 2], che non è la stessa cosa.

Input: next = [-1]
Output: [-1]
Spiegazione: Un nodo è l’inverso di se stesso. Rimane sia la testa sia la coda e continua a collegarsi a -1.

+11 test nascosti all’invio

Per approfondire

Riesci a invertire solo la parte della lista compresa tra la posizione left e la posizione right, lasciando i nodi prima e dopo al loro posto?

Suggerimenti

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

0 di 3 aperti

Soluzione

Invertire una lista non sposta alcun nodo; capovolge ogni collegamento. Il problema è che il collegamento di un nodo è l’unico modo per raggiungere il resto della lista, quindi nel momento in cui lo sovrascrivi, tutto ciò che viene dopo va perso. Puoi evitare il problema annotando prima l’ordine, oppure puoi percorrere la lista una volta usando tre puntatori che salvano il percorso da seguire prima di capovolgere ogni collegamento.

Annota l’ordine, poi ricollega

Intuizione

In questo problema un puntatore è l'indice di un nodo e spostarsi in avanti significa node = next[node]. Parti dal nodo 0 e prosegui finché non raggiungi -1, annotando ogni nodo attraversato. Nel secondo esempio, l'ordine ottenuto è [0, 2, 3, 1].

Nella lista invertita, ogni nodo è collegato al nodo che lo precedeva in quell'ordine: 1 è collegato a 3, 3 a 2, 2 a 0. Il primo nodo dell'ordine, la vecchia testa, non ha nessun nodo che lo precede, quindi è collegato a -1. Riempi un nuovo array con questi collegamenti e restituiscilo.

Poiché ogni collegamento viene scritto in un nuovo array, non sovrascrivi nulla mentre ti serve ancora: così è difficile sbagliare con questa versione. Richiede O(n) tempo e O(n) memoria aggiuntiva per l'ordine e il nuovo array.

Algoritmo

Percorri i nodi da 0 a -1 e aggiungi ogni nodo a order.
Crea un nuovo array della stessa lunghezza.
Imposta la voce di order[0] su -1.
Per ogni k ≥ 1, imposta la voce di order[k] su order[k-1].
Restituisci il nuovo array.

def reverseList(next):
    order = []
    node = 0
    while node != -1:
        order.append(node)
        node = next[node]
    reversed_next = [0] * len(next)
    reversed_next[order[0]] = -1  # the old head ends the new list
    for k in range(1, len(order)):
        reversed_next[order[k]] = order[k - 1]
    return reversed_next

Inverti i collegamenti in un solo passaggio

Intuizione

Puoi invertire ogni collegamento non appena raggiungi il suo nodo, se ricordi il nodo da cui provieni. Mantieni prev, il nodo alle tue spalle, inizializzato a -1 perché la vecchia testa diventerà l'ultimo nodo. In node, il collegamento next[node] punta in avanti; impostalo a prev in modo che punti all'indietro.

Questa scrittura distrugge il tuo unico modo per proseguire, quindi salvalo prima in una terza variabile, after = next[node]. Poi inverti il collegamento e sposta entrambi i puntatori di un passo: prev = node, node = after. In ogni momento, i nodi alle tue spalle formano una lista invertita con testa prev, mentre i nodi davanti a te sono il resto non modificato, che inizia da node. Quando node raggiunge -1, tutti i collegamenti sono stati invertiti e prev è la nuova testa.

Nel secondo esempio i puntatori attraversano i nodi 0, 2, 3, 1, scrivendo next[0] = -1, next[2] = 0, next[3] = 2 e next[1] = 3. Ogni nodo viene visitato una volta, tempo O(n), e l'unica memoria utilizzata è di tre interi, O(1).

Algoritmo

Imposta prev = -1 e node = 0.
Mentre node non è -1, salva after = next[node].
Imposta next[node] = prev.
Procedi: prev = node, poi node = after.
Restituisci next.

def reverseList(next):
    prev = -1  # the node behind the current one; the old head will point to -1
    node = 0
    while node != -1:
        after = next[node]  # save the rest of the list before cutting the link
        next[node] = prev
        prev = node
        node = after
    return next

Trappole e casi limite

Quasi tutti i bug qui riguardano l’ordine delle tre assegnazioni o le due estremità della lista.

Sovrascrivere next[node] prima di salvarlo. Dopo next[node] = prev, il vecchio collegamento in avanti è scomparso e la visita torna indietro invece di proseguire verso il nodo successivo.
Inizializzare prev con un valore diverso da -1. La vecchia testa deve terminare la nuova lista. Inizializzandolo con 0, il nodo 0 punta a sé stesso.
Invertire l’array invece dei collegamenti. I nodi non sono memorizzati nell’ordine della lista e la risposta mantiene ogni nodo al proprio indice; cambiano solo i valori. Invertire [2, -1, 3, 1] dà [1, 3, -1, 2], non [-1, 3, 0, 2].
Fermarsi un nodo troppo presto usando un ciclo con next[node] != -1. Anche il collegamento dell’ultimo nodo deve essere invertito, quindi il ciclo deve continuare finché node != -1.
Invertire una lista lunga con la ricorsione. Una lista di 5000 nodi richiede 5000 chiamate annidate, superando il limite di Python di 1000.
Dimenticare l’offset in Lua e R, dove gli array iniziano da 1. Mantieni gli indici dei nodi a partire da 0 e leggi next[node + 1]. Ruby e R riservano la parola next, quindi nei loro esempi iniziali il parametro si chiama next_.

Domande frequenti4

Come si inverte una lista concatenata sul posto?

Percorri la lista con due puntatori: prev inizializzato a niente e node inizializzato alla testa. Per ogni nodo, salva il nodo successivo, imposta il suo collegamento a prev, quindi sposta prev e node avanti di un passo. Quando node termina, prev è la testa della lista invertita.

Qual è la complessità temporale e spaziale dell’inversione di una lista concatenata?

La versione iterativa visita ogni nodo una volta, tempo O(n), e mantiene tre puntatori, spazio aggiuntivo O(1). Copiare prima l’ordine in un array richiede anch’esso tempo O(n), ma necessita di spazio aggiuntivo O(n). Una versione ricorsiva usa O(n) di spazio per lo stack delle chiamate.

Riesci a invertire ricorsivamente una lista concatenata?

Sì. Inverti tutto ciò che viene dopo la testa, poi fai in modo che il vecchio nodo successivo della testa punti di nuovo alla testa e imposta a niente il collegamento della testa. Si legge bene, ma effettua una chiamata annidata per ogni nodo, quindi una lista lunga può causare l'overflow dello stack delle chiamate. Python si ferma a 1000 chiamate per impostazione predefinita, un limite superato da una lista di 5000 nodi.

Perché per invertire una lista concatenata servono tre puntatori?

Per invertire il collegamento di un nodo ti servono il nodo stesso e quello che lo precede, ovvero due puntatori. Il terzo punta al nodo successivo, perché invertire il collegamento cancella l’unico riferimento al resto della lista. Senza di esso, la visita non può proseguire.

Python

def reverseList(next):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

next = [1, 2, 3, -1]

Atteso

[-1, 0, 1, 2]