Remove Nth Node From End of List
Hai una lista concatenata singola memorizzata in due array della stessa lunghezza. Il nodo i contiene il valore values[i] e 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.
Rimuovi l’n-esimo nodo contando dalla fine della lista, dove l’ultimo nodo è il 1º dalla fine. Restituisci i valori dei nodi rimanenti, nell’ordine della lista.
Funzione
- valuesinteger-array
- il valore contenuto in ciascun nodo
- nextinteger-array
- l'indice del nodo a cui è collegato ciascun nodo, oppure -1 per l'ultimo nodo
- ninteger
- quale nodo rimuovere, contando dalla fine, dove 1 è l’ultimo nodo
- Restituisceinteger-array
- i valori rimanenti nell'ordine della lista, vuota quando viene rimosso l'unico nodo
Vincoli
1 ≤ L ≤ 5000, doveLè la lunghezza divaluese dinext.-100 ≤ values[i] ≤ 1001 ≤ n ≤ L- Ogni
next[i]è-1oppure un indice di nodo da0aL-1. - Partendo dal nodo
0, la lista visita ogni nodo esattamente una volta e poi raggiunge-1. Non c'è alcun ciclo.
Esempi
- Input
- values = [5, 9, 2, 7, 6]next = [2, 3, 4, -1, 1]n = 2
- Output
- [5, 2, 6, 7]
- Spiegazione
- Seguendo i collegamenti a partire dal nodo
0, si visitano i nodi0, 2, 4, 1, 3, quindi la lista è5, 2, 6, 9, 7. Il 2º elemento dalla fine è il nodo1, valore9, e senza di esso la lista è5, 2, 6, 7. L'elemento dell'arrayvalues[5-2] = 7è l'ultimo nodo, non quello da rimuovere.
- Input
- values = [10, 20, 30, 40]next = [1, 2, 3, -1]n = 4
- Output
- [20, 30, 40]
- Spiegazione
- Quattro nodi e
n = 4: il 4º nodo a partire dalla fine è la testa. La lista ora inizia dal nodo1e contiene20, 30, 40.
- Input
- values = [42]next = [-1]n = 1
- Output
- []
- Spiegazione
- L’unico nodo è sia la testa sia l’ultimo nodo. Rimuovendolo, la lista rimane vuota, quindi la risposta è
[].
+14 test nascosti all’invio
Per approfondire
Riesci a trovare e scollegare il nodo in un unico passaggio, senza prima contarne la lunghezza?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Una lista procede solo in avanti e il nodo è definito dalla sua distanza dalla fine. Se conoscessi la lunghezza
L, in quale posizione dall’inizio si troverebbe? E il collegamento di quale nodo devi modificare per rimuoverlo?Puoi misurare la distanza dalla fine senza conoscere la lunghezza. Fai partire un puntatore
ncollegamenti avanti rispetto a un altro e spostali insieme. Quando il primo si trova sull’ultimo nodo, il secondo si trova subito prima del nodo da rimuovere.Sposta
fastin avantinvolte. Se ora è-1, la testa è il nodo da rimuovere, quindi la lista inizia danext[0]. Altrimenti spostaslowefastinsieme finchénext[fast] != -1, poi impostanext[slow] = next[next[slow]]. Percorri la lista dalla testa e raccogli i valori.
Soluzione
Il bersaglio è definito dalla sua distanza dalla fine, ma una lista concatenata semplice permette solo di procedere in avanti, e si scopre dov’è la fine solo quando la si raggiunge. Per rimuovere un nodo bisogna anche trovarsi sul nodo che lo precede, perché è il collegamento di quel nodo a cambiare. Puoi copiare la lista in un array oppure contarne gli elementi e percorrerla di nuovo. La soluzione classica mantiene due puntatori separati da n collegamenti, in modo che, quando quello davanti raggiunge l’ultimo nodo, quello dietro si trovi subito prima del bersaglio. Qui sotto, L è il numero di nodi.
Copia i valori in un array
Intuizione
In questo problema un puntatore è un indice di nodo. Avanzare significa node = next[node] e raggiungere -1 vuol dire che hai superato la fine. Nel primo esempio il percorso dal nodo 0 è 0 → 2 → 4 → 1 → 3 → -1.
Contare dalla fine è difficile solo perché una lista non ha posizioni. Quindi assegnale delle posizioni: percorrila una volta e aggiungi ogni valore a un array. Nel primo esempio quell'array è [5, 2, 6, 9, 7]. In un array di L valori l'ultimo si trova all'indice L-1, quindi l'n-esimo dalla fine si trova all'indice L-n. Qui è 5-2 = 3, il 9. Eliminalo e restituisci [5, 2, 6, 7].
È corretto e richiede O(L) tempo, ma copia l'intera lista e non modifica mai un collegamento. Lo scopo del problema è modificare la lista stessa, con memoria aggiuntiva O(1), ed è ciò che fanno i due approcci successivi.
Algoritmo
- Inizia con un array vuoto e
node = 0. - Mentre
nodeè diverso da-1, aggiungivalues[node]e passa anext[node]. - Elimina la voce all’indice
length - n. - Restituisci l’array.
def removeNthFromEnd(values, next, n):
# Write the values out in list order.
order = []
node = 0
while node != -1:
order.append(values[node])
node = next[node]
# Counting from the end, the n-th value sits at index len(order) - n.
del order[len(order) - n]
return orderConta i nodi, poi scollegali
Intuizione
Per rimuovere un nodo da una lista, modifichi il collegamento del nodo che lo precede in modo che lo salti: next[prev] = next[next[prev]]. Il nodo rimosso è ancora negli array, ma nessun percorso dalla testa lo raggiunge più.
Quindi trova prev. Conta i nodi con una prima percorrenza. Considerando la testa come posizione 0, il nodo obiettivo si trova alla posizione L-n e il nodo che lo precede alla posizione L-n-1, a cui arrivi dalla testa in L-n-1 passaggi. Nel primo esempio L = 5 e n = 2: due passaggi 0 → 2 → 4 ti portano al nodo 4, che è collegato al nodo 1, il 9. Impostando next[4] = next[1] = 3, la lista diventa 5, 2, 6, 7.
In un caso non c'è alcun nodo che precede quello obiettivo: n = L, quando il nodo obiettivo è la testa. In tal caso non è necessario modificare alcun collegamento. La lista inizia da next[0] invece che da 0, come nel secondo esempio. Poi percorri la lista dalla testa per raccogliere la risposta. Due percorrenze della lista richiedono circa 2L passaggi e la memoria oltre a quella necessaria per la risposta è di pochi interi.
Algoritmo
- Procedi dal nodo
0a-1e conta i nodi comeL. - Se
n == L, la nuova testa ènext[0]. - Altrimenti, imposta
prevsul nodo0e fallo avanzare diL-n-1posizioni, poi impostanext[prev] = next[next[prev]]. - Procedi dalla testa e raccogli
values[node]in ordine.
def removeNthFromEnd(values, next, n):
# First pass: count the nodes.
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
head = 0
if n == length:
# The node to remove is the head, so the list starts at its second node.
head = next[0]
else:
# Second pass: stop on the node just before position length - n.
prev = 0
for _ in range(length - n - 1):
prev = next[prev]
next[prev] = next[next[prev]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return resultDue puntatori distanti n collegamenti
Intuizione
Puoi misurare «n dalla fine» senza conoscere L. Fai avanzare fast di n nodi mentre slow resta in attesa sulla testa. Poi fai avanzare entrambi di un nodo alla volta. La distanza rimane n, quindi quando fast si trova sull’ultimo nodo (next[fast] == -1, posizione L-1), slow si trova alla posizione L-1-n: il nodo subito prima di quello da eliminare. Un’istruzione next[slow] = next[next[slow]] elimina il nodo da eliminare.
Segui il primo esempio. fast fa due passi, 0 → 2 → 4. Ora avanzano entrambi: slow arriva a 2 mentre fast arriva a 1, poi slow arriva a 4 mentre fast arriva a 3. Il nodo 3 è l’ultimo, quindi ti fermi. next[4] è il nodo 1, il 9, e impostando next[4] = next[1] = 3 lo elimini.
Il caso della testa si presenta da sé. Poiché n ≤ L, fast raggiunge -1 durante il suo avanzamento iniziale solo quando n = L, ed è proprio in quel caso che la testa è il nodo da eliminare. Con gli oggetti nodo, inseriresti un nodo fittizio davanti alla testa per far scomparire questo caso; qui il controllo fast == -1 svolge lo stesso compito. Trovare e scollegare il nodo richiede un solo passaggio. Scrivere la risposta richiede un’ulteriore scansione, necessaria con qualsiasi approccio.
Algoritmo
- Imposta
fast = 0e fallo avanzare dinposizioni confast = next[fast]. - Se
fast == -1, la testa è il nodo obiettivo: la nuova testa ènext[0]. - Altrimenti imposta
slow = 0e fai avanzare entrambi finchénext[fast] != -1. - Imposta
next[slow] = next[next[slow]]. - Percorri la lista dalla testa e raccogli
values[node]nell’ordine.
def removeNthFromEnd(values, next, n):
# Send fast n links ahead of slow.
fast = 0
for _ in range(n):
fast = next[fast]
head = 0
if fast == -1:
# Fast fell off the end, so the list has exactly n nodes: remove the head.
head = next[0]
else:
# Move both, keeping the gap. When fast stands on the last node,
# slow stands just before the node to remove.
slow = 0
while next[fast] != -1:
slow = next[slow]
fast = next[fast]
next[slow] = next[next[slow]] # skip over the removed node
result = []
node = head
while node != -1:
result.append(values[node])
node = next[node]
return result
Trappole e casi limite
La maggior parte delle risposte errate dipende dal punto in cui si ferma il nodo inseguitore e dal caso in cui viene rimosso il nodo di testa.
- Rimuovere l'elemento all'indice
L-ndell'array. I nodi non sono memorizzati nell'ordine della lista, quindi di solito quell'indice corrisponde a un altro nodo. Nel primo esempiovalues[3] = 7è l'ultimo nodo, non il9. - Fermarsi quando
fast == -1invece che quandonext[fast] == -1. In questo modoslowavanza di un passo di troppo e arriva sul nodo da rimuovere; in una lista semplicemente concatenata non puoi scollegare un nodo partendo dal nodo stesso. - Dimenticare il caso del nodo di testa. Quando
n = L, dopo il suo avanzamento inizialefastè-1, e leggerenext[fast]causa un errore nella maggior parte dei linguaggi. Python leggenext[-1]senza lamentarsi e restituisce una lista errata, più difficile da individuare. - Scollegare il nodo con
next[slow] = next[slow] + 1oslow + 2. I nodi vicini nella lista non sono vicini negli array; l'unico modo per raggiungere il nodo successivo a quello da rimuovere ènext[next[slow]]. - Raccogliere la risposta partendo dal nodo
0dopo che è stato rimosso il nodo di testa. Inizia la scansione finale dal nuovo nodo di testa. - 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 parolanext, quindi nei loro esempi il parametro si chiamanext_.
Domande frequenti4
Come si rimuove il nodo n-esimo dalla fine di una lista concatenata in un'unica passata?
Usa due puntatori con una distanza di n. Sposta il primo avanti di n nodi, poi muovili entrambi insieme finché il primo non si trova sull’ultimo nodo. A questo punto il secondo si trova subito prima del nodo da rimuovere, quindi fai puntare il suo collegamento oltre quel nodo. Se il primo puntatore esce dalla lista durante il suo vantaggio iniziale, il nodo da rimuovere è la testa.
Perché le soluzioni a questo problema usano un nodo fittizio?
Rimuovere un nodo significa modificare il collegamento del nodo che lo precede, e la testa non ha un nodo che la preceda. Un nodo fittizio posizionato davanti alla testa assegna a ogni nodo, testa inclusa, un predecessore, così una sola riga di scollegamento copre tutti i casi. La risposta inizia quindi dal nodo successivo a quello fittizio. Controllare se il puntatore iniziale è uscito dalla lista dopo n passaggi gestisce lo stesso caso senza il nodo aggiuntivo.
Qual è la complessità temporale e spaziale della rimozione dell’n-esimo nodo dalla fine?
Per un elenco di L nodi occorre un tempo O(L), perché devi raggiungere la fine per sapere dove si trova l’elemento cercato. Sia il conteggio iniziale sia il metodo dei due puntatori usano una memoria aggiuntiva O(1). Copiare i valori in un array richiede O(L).
La soluzione con due puntatori è più veloce che contare prima la lunghezza?
Non di molto: entrambi sono O(L) e, insieme, i due puntatori fanno comunque all'incirca tanti spostamenti quanti ne farebbero due percorrenze. Il vero vantaggio è che non devi conoscere prima la lunghezza, quindi il metodo funziona anche quando la lista arriva come flusso che puoi leggere una sola volta. È proprio questo singolo passaggio che di solito gli intervistatori richiedono.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def removeNthFromEnd(values, next, n):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
values = [5, 9, 2, 7, 6] next = [2, 3, 4, -1, 1] n = 2
Atteso
[5, 2, 6, 7]