Palindrome Linked List
Ti viene fornita una lista concatenata singolarmente memorizzata in due array della stessa lunghezza. Il nodo i contiene il valore values[i] e punta al nodo next[i]; -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.
Restituisci true se i valori letti dalla testa alla fine sono uguali a quelli letti dalla fine alla testa, e false altrimenti.
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
- Restituisceboolean
- vero se la lista si legge allo stesso modo in entrambe le direzioni
Vincoli
1 ≤ L ≤ 5000, doveLè la lunghezza dinexte divalues.-100 ≤ values[i] ≤ 100- 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
- next = [4, 3, -1, 2, 1]values = [3, 4, 3, 1, 1]
- Output
- true
- Spiegazione
- I collegamenti visitano i nodi
0, 4, 1, 3, 2, quindi la lista è3, 1, 4, 1, 3. I due 3 corrispondono, i due 1 corrispondono e il4al centro non ha un elemento corrispondente da controllare.
- Input
- next = [2, -1, 3, 1]values = [4, 4, 9, 9]
- Output
- true
- Spiegazione
- La lista visita i nodi
0, 2, 3, 1e legge4, 9, 9, 4, allo stesso modo in entrambe le direzioni.
- Input
- next = [2, -1, 1]values = [1, 2, 1]
- Output
- false
- Spiegazione
- L'array
valuesè[1, 2, 1], ma l'elenco visita i nodi0, 2, 1e legge1, 1, 2. Al contrario è2, 1, 1, quindi la risposta èfalse.
Per approfondire
Riesci a farlo in O(L) in tempo con O(1) memoria aggiuntiva?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Un controllo del palindromo confronta il primo valore con l'ultimo, il secondo con il penultimo e così via. In una lista concatenata semplice puoi procedere solo in avanti. Che cosa renderebbe raggiungibile la parte finale?
Copiare i valori in un array nell’ordine della lista funziona, ma richiede
O(L)di memoria. Senza la copia, la seconda metà deve essere percorsa all’indietro. Modificarne i collegamenti può renderlo possibile.Trova il centro con due puntatori:
fastavanza di due collegamenti ogni volta cheslowavanza di uno. Quandofastnon può più avanzare,slowsi trova alla fine della prima metà. Inverti i collegamenti doposlow, poi procedi contemporaneamente dalla testa e dal vecchio ultimo nodo e confronta.
Soluzione
Un controllo di palindromo abbina ogni valore al suo speculare dall'altra estremità. Una lista concatenata semplice procede solo in avanti, quindi la parte difficile è leggere al contrario la metà posteriore. Una copia in un array lo fa usando O(L) di memoria, dove L è il numero di nodi; invertire i collegamenti della seconda metà lo fa usando O(1).
Copia i valori in un array
Intuizione
Un puntatore qui è un indice di nodo e procedere in avanti significa node = next[node]. Scorri la lista una volta e copia ogni valore in un array, che puoi leggere da entrambe le estremità. Confronta il primo e l’ultimo valore, sposta entrambi gli indici verso il centro e restituisci false se non corrispondono. Con una lunghezza dispari, il valore centrale è il partner di sé stesso.
È necessario leggere ogni valore, quindi O(L) è il tempo minimo possibile. Il costo è di L interi aggiuntivi.
Algoritmo
- Procedi dal nodo
0a-1e aggiungi ognivalues[node]a un array. - Imposta
i = 0ejsull'ultimo indice. - Mentre
i < j, restituiscifalsese i due valori sono diversi, altrimenti incrementaie decrementaj. - Restituisci
true.
def isPalindrome(next, values):
# Write the values out in list order.
seq = []
node = 0
while node != -1:
seq.append(values[node])
node = next[node]
# Compare from both ends toward the middle.
i = 0
j = len(seq) - 1
while i < j:
if seq[i] != seq[j]:
return False
i += 1
j -= 1
return TrueInverti la seconda metà sul posto
Intuizione
Inverti i collegamenti della seconda metà invece di copiarla: una visita a partire dal vecchio ultimo nodo conduce quindi verso il centro. Per trovare il centro, sposta fast di due collegamenti per ogni collegamento percorso da slow, finché fast ha due collegamenti davanti a sé. slow si ferma sull’ultimo nodo della prima metà, il nodo centrale quando L è dispari. Nel primo esempio slow percorre 0 → 4 → 1 mentre fast percorre 0 → 1 → 2, quindi slow si ferma su 4.
Inverti i nodi dopo slow, poi percorri insieme left dalla testa e right dalla metà invertita: 3 con 3, poi 1 con 1. La metà invertita non è mai più lunga della prima metà, quindi fermandoti quando right termina confronti esattamente le coppie che contano. Ogni fase percorre al massimo L nodi e memorizza pochi interi. In R, modificare next_ copia il vettore una volta, quindi R usa memoria O(L).
Algoritmo
- Imposta
slow = fast = 0. Mentrenext[fast]enext[next[fast]]sono entrambi diversi da-1, spostaslowdi un collegamento efastdi due. - Inverti la lista che inizia da
next[slow]: per ogni nodo, salva il suo collegamento, puntalo aprev, poi spostapreve il nodo in avanti. - Imposta
left = 0eright = prev, la testa della metà invertita. - Mentre
right != -1, restituiscifalsein caso di mancata corrispondenza, altrimenti sposta entrambi i puntatori di un collegamento. - Restituisci
true.
def isPalindrome(next, values):
# Find the middle: fast moves two links for every one link slow moves.
slow = 0
fast = 0
while next[fast] != -1 and next[next[fast]] != -1:
slow = next[slow]
fast = next[next[fast]]
# slow is the last node of the first half (the middle node when the length is odd).
# Reverse the links of the second half.
prev = -1
node = next[slow]
while node != -1:
after = next[node]
next[node] = prev
prev = node
node = after
# prev is the old last node, now the head of the reversed half.
left = 0
right = prev
while right != -1:
if values[left] != values[right]:
return False
left = next[left]
right = next[right]
return True
Trappole e casi limite
- Controllare gli array invece della lista. Nel terzo esempio
valuesè[1, 2, 1], ma la lista è1, 1, 2. - Verificare solo
next[fast] != -1.fastpuò quindi passare a-1e leggerenext[-1], che nella maggior parte dei linguaggi è fuori dai limiti e in Python e Ruby indica silenziosamente l'ultimo elemento. - Confrontare finché non termina
leftinvece diright. Il nodo centrale è ancora collegato alla vecchia seconda metà, quindi il percorso dalla testa è quello più lungo. - Sovrascrivere
next[node]durante l'inversione prima di salvarlo, perdendo così il resto della lista. - In Lua e R, dove gli array iniziano da 1, leggere
next[node]per un ID del nodo basato su 0. Legginext[node + 1].
Domande frequenti3
Qual è la complessità temporale della verifica di una lista concatenata palindroma?
Ogni approccio è O(L) per una lista di L nodi, perché ogni valore deve essere confrontato. Copiare i valori in un array o inserirli in uno stack usa O(L) di memoria aggiuntiva; invertire sul posto la seconda metà usa O(1).
In che modo il puntatore veloce e quello lento trovano il centro di una lista concatenata?
Entrambi partono dalla testa e il puntatore veloce compie due passi per ogni passo di quello lento. Quando il puntatore veloce raggiunge la fine, ha percorso l’intera lista, mentre quello lento ne ha percorso la metà.
Invertire metà dell'elenco distrugge l'input?
Sì, modifica i collegamenti della seconda metà e, nella maggior parte dei linguaggi, quell’array appartiene al chiamante. Se ti serve ancora la lista, completa il confronto senza restituire il controllo in anticipo, poi inverti di nuovo quella metà. Il nodo centrale continua a puntare al primo nodo della metà, quindi la lista è di nuovo intera usando O(1) memoria aggiuntiva.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def isPalindrome(next, values):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
next = [4, 3, -1, 2, 1] values = [3, 4, 3, 1, 1]
Output atteso
true