Middle of the Linked List
Ti viene fornita 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.
Restituisci il valore del nodo centrale. Quando la lista ha un numero pari di nodi, ci sono due nodi centrali; restituisci il valore del secondo.
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
- Restituisceinteger
- il valore del nodo centrale, il secondo nodo centrale quando la lunghezza è pari
Vincoli
1 ≤ n ≤ 5000, dovenè la lunghezza divaluese dinext.-104 ≤ values[i] ≤ 104- 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
- values = [4, 9, 2, 7, 5]next = [3, -1, 1, 4, 2]
- Output
- 5
- Spiegazione
- Seguendo i collegamenti dal nodo
0si ottengono i nodi0, 3, 4, 2, 1, quindi la lista contiene4, 7, 5, 2, 9. Il terzo dei cinque è il nodo4, il cui valore è5. L'elemento centrale dell'array stesso,values[2] = 2, è un nodo diverso.
- Input
- values = [10, 20, 30, 40, 50, 60]next = [1, 2, 3, 4, 5, -1]
- Output
- 40
- Spiegazione
- Qui i nodi sono memorizzati in ordine. Con sei nodi ce ne sono due al centro,
30e40, e vince il secondo.
- Input
- values = [8]next = [-1]
- Output
- 8
- Spiegazione
- Una lista composta da un solo nodo ha il nodo stesso come elemento centrale.
+13 test nascosti all’invio
Per approfondire
Riesci a restituire il nodo che si trova a un terzo del percorso lungo la lista in un solo passaggio? A quale velocità si muoverebbe ciascun puntatore e dove ti fermeresti?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Non conosci la lunghezza della lista finché non ne raggiungi la fine. E se due camminatori partissero dall’inizio e uno dei due si muovesse a una velocità doppia rispetto all’altro?
Quando il camminatore più veloce ha raggiunto la fine, quello più lento ha percorso metà della distanza, quindi si trova sul nodo centrale. L’unico dettaglio rimasto è quando fermarsi affinché, in caso di lunghezza pari, ci si trovi sul secondo nodo centrale.
Inizia
slowefastdal nodo0. Mentrefastè diverso da-1enext[fast]è diverso da-1, sposta slow di un collegamento e fast di due collegamenti. Poi restituiscivalues[slow].
Soluzione
In un array il centro si trova all'indice n / 2. Una lista concatenata non ha indici: puoi scoprire quanto è lunga solo percorrendola fino alla fine, e a quel punto hai già superato il centro. Puoi copiare la lista in un array oppure prima contarne gli elementi e poi percorrerla di nuovo. La soluzione elegante fa avanzare due puntatori nella lista a velocità diverse, così quello lento si trova a metà quando quello veloce arriva alla fine.
Copia i valori in un array
Intuizione
In questo problema un puntatore è l’indice di un nodo. Per spostarsi al nodo successivo si usa node = next[node], e raggiungere -1 significa essere arrivati oltre la fine. Nel primo esempio, il percorso dal nodo 0 è 0 → 3 → 4 → 2 → 1 → -1.
Il problema di una lista è che non puoi saltare direttamente a una posizione. Quindi trasformala in qualcosa che te lo permetta: percorri la lista una volta e aggiungi ogni valore a un nuovo array man mano che lo incontri. L’array contiene i valori nell’ordine della lista: [4, 7, 5, 2, 9] nel primo esempio, e il suo elemento centrale si trova all’indice length / 2 con la divisione intera.
Per una lunghezza pari, quell’indice individua da solo il secondo elemento centrale: sei valori danno l’indice 3, il quarto valore, che nel secondo esempio è 40. Il percorso richiede un tempo O(n) e la copia richiede O(n) di memoria aggiuntiva, che i due approcci successivi evitano.
Algoritmo
- Inizia con un array vuoto e
node = 0. - Finché
nodenon è-1, aggiungivalues[node]e passa anext[node]. - Restituisci l'elemento all'indice
length / 2, arrotondato per difetto.
def middleNode(values, next):
in_order = []
node = 0
while node != -1:
in_order.append(values[node])
node = next[node]
return in_order[len(in_order) // 2]Conta, poi cammina a metà strada
Intuizione
Non ti serve copiare l'intera lista, solo la sua lunghezza. Percorri la lista una volta e conta i nodi. Poi riparti dalla testa e fai length / 2 passi, arrotondando per difetto. Il nodo su cui ti fermi è quello centrale.
Perché proprio quel numero di passi: dopo k passi ti trovi sul nodo in posizione k, contando la testa come posizione 0. Il nodo centrale di una lista di 5 è in posizione 2, mentre il secondo nodo centrale di una lista di 6 è in posizione 3: in entrambi i casi, length / 2. Nel primo esempio conti 5, fai due passi 0 → 3 → 4 e leggi values[4] = 5.
Ora la memoria è O(1). Il costo è un secondo passaggio su metà della lista, per un totale di 1.5n spostamenti, che è comunque O(n).
Algoritmo
- Procedi dal nodo
0a-1e conta i nodi. - Torna al nodo
0. - Esegui
node = next[node]esattamentecount / 2volte, arrotondando per difetto. - Restituisci
values[node].
def middleNode(values, next):
length = 0
node = 0
while node != -1:
length += 1
node = next[node]
node = 0
for _ in range(length // 2):
node = next[node]
return values[node]Il puntatore veloce e quello lento
Intuizione
Posiziona due puntatori all’inizio. A ogni iterazione, slow avanza di un nodo e fast di due. Dopo k iterazioni, slow si trova alla posizione k e fast alla posizione 2k, quindi slow ha sempre percorso metà della distanza di fast. Quando fast raggiunge la fine, slow si trova a metà e non hai mai avuto bisogno di conoscere la lunghezza.
La condizione di arresto determina quale dei due nodi centrali ottieni. Continua finché fast è un nodo effettivo e ha un nodo dopo di sé: fast != -1 e next[fast] != -1. Con una lunghezza dispari, fast si ferma sull’ultimo nodo. Con una lunghezza pari, fast supera la fine e arriva a -1, il che fa avanzare slow di un nodo in più, fino al secondo nodo centrale. Nel secondo esempio slow passa per 0, 1, 2, 3 mentre fast passa per 0, 2, 4, -1, e values[3] è 40.
Nel primo esempio slow visita i nodi 0, 3, 4 mentre fast visita 0, 4, 1; il nodo 1 è l’ultimo, quindi il ciclo si ferma con slow sul nodo 4 e la risposta è 5. Fast compie circa n spostamenti e slow n / 2, in un’unica scansione e usando due interi di memoria.
Algoritmo
- Imposta
slow = 0efast = 0. - Finché
fast != -1enext[fast] != -1, impostaslow = next[slow]efast = next[next[fast]]. - Restituisci
values[slow].
def middleNode(values, next):
slow = fast = 0
# Stop when fast is on the last node or has stepped past it.
while fast != -1 and next[fast] != -1:
slow = next[slow]
fast = next[next[fast]]
return values[slow]
Trappole e casi limite
Il ciclo è breve, quindi gli errori riguardano il punto in cui inizia, quello in cui si ferma e ciò che restituisce.
- Restituire
values[n / 2]. I nodi non sono memorizzati nell'ordine della lista, quindi l'elemento centrale dell'array è di solito un altro nodo. Nel primo esempio restituisce2invece di5. - Ottenere il primo nodo centrale con una lunghezza pari. Un ciclo che continua finché
next[fast]enext[next[fast]]sono entrambi validi si ferma un giro prima e restituisce30invece di40nel secondo esempio. - Controllare
next[fast]prima difast != -1. Con una lunghezza pari, fast diventa-1e leggerenext[-1]causa un errore nella maggior parte dei linguaggi. In Python legge silenziosamente l'ultimo elemento, il che è peggio. - Avanzare di
count / 2 - 1o arrotondare per eccesso nell'approccio con il conteggio. Conta la testa come posizione0e fai esattamentecount / 2passi, arrotondando per difetto. - Restituire l'indice del nodo invece del suo valore.
- 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 relativi esempi iniziali il parametro si chiamanext_.
Domande frequenti4
Perché i puntatori veloce e lento trovano il centro di una lista collegata?
Entrambi partono dalla testa e, a ogni iterazione, il puntatore veloce avanza di due nodi mentre quello lento ne avanza uno. Dopo k iterazioni, il puntatore veloce si trova alla posizione 2k e quello lento alla posizione k, esattamente a metà strada. Quindi, quando il puntatore veloce raggiunge la fine della lista, quello lento si trova al centro.
Qual è la complessità temporale e spaziale per trovare l’elemento centrale di una lista concatenata?
Tutti e tre gli approcci richiedono un tempo O(n), poiché non è possibile trovare l’elemento centrale senza percorrere circa metà della lista o più. Copiare i valori richiede O(n) di memoria aggiuntiva. Il conteggio iniziale e i puntatori veloce e lento richiedono entrambi O(1), e i puntatori necessitano di un solo passaggio.
Come si restituisce il primo nodo centrale invece del secondo?
Modifica la condizione di arresto in modo che il puntatore veloce si fermi un giro prima: esegui il ciclo finché next[fast] != -1 e next[next[fast]] != -1. Con sei nodi, il puntatore lento si ferma quindi alla posizione 2 invece che alla 3. Nell’approccio basato sul conteggio, avanza di (count - 1) / 2 passi invece che di count / 2.
Dove viene utilizzata la tecnica dei puntatori veloce e lento?
Le stesse due velocità rilevano un ciclo in una lista concatenata: in un ciclo, il puntatore veloce raggiunge quello lento e si incontrano. Trovano anche il punto in cui inizia un ciclo e dividono una lista a metà per il merge sort o per verificare se una lista si legge allo stesso modo in entrambe le direzioni.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def middleNode(values, next):
# Scrivi qui il codiceCaso 1
Caso 2
Caso 3
Input
values = [4, 9, 2, 7, 5] next = [3, -1, 1, 4, 2]
Atteso
5