Unire, dividere e trovare l'ennesimo elemento dalla fine
Unisca due liste concatenate ordinate in O(n), divida una lista a metà usando puntatori lento e veloce e trovi l'ennesimo nodo dalla coda
Unire, dividere e trovare l'ennesimo elemento dalla fine è una lezione Coding Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento Coding Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso Coding Interview Prep include 4 lezioni in totale.
Tre schemi essenziali per le liste concatenate
Questa lezione tratta tre operazioni fondamentali sulle liste concatenate, che compaiono continuamente come elementi costitutivi di problemi più complessi: unire due liste ordinate (utilizzato nel merge sort e nell'unione K-way), suddividere una lista in corrispondenza del punto centrale (utilizzato nel merge sort e nel rilevamento dei palindromi) e trovare il nodo n-esimo dalla fine (utilizzato in remove-nth-from-end).
Tutte e tre si basano su tecniche già viste: il nodo testa fittizio, i puntatori lento e veloce e il tracciamento attento dei confini.
Unire due liste ordinate
LeetCode 21, «Merge Two Sorted Lists»: date due liste concatenate ordinate, restituire un'unica lista concatenata ordinata risultante dalla loro unione. Utilizzare una testa fittizia e un puntatore di coda curr. A ogni passo, confrontare le teste delle due liste e collegare a curr il nodo più piccolo. Quando una lista è esaurita, collegare il segmento rimanente dell'altra. Tempo: O(n+m), spazio: O(1) (ricollegamento in loco).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1
l1 = l1.next
else:
curr.next = l2
l2 = l2.next
curr = curr.next
curr.next = l1 or l2 # attach remaining nodes
return dummy.next
def build(arr):
d = ListNode(); c = d
for v in arr:
c.next = ListNode(v); c = c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
print(to_list(mergeTwoLists(build([1,2,4]), build([1,3,4]))))Tracciare l'unione passo per passo
Tracciamo mergeTwoLists([1,2,4], [1,3,4]): confrontiamo 1 e 1 — scegliamo l1(1) e facciamo avanzare l1 a 2. Confrontiamo 2 e 1 — scegliamo l2(1) e facciamo avanzare l2 a 3. Confrontiamo 2 e 3 — scegliamo l1(2) e facciamo avanzare l1 a 4. Confrontiamo 4 e 3 — scegliamo l2(3) e facciamo avanzare l2 a 4. Confrontiamo 4 e 4 — scegliamo l1(4) e facciamo avanzare l1 a None. Colleghiamo l2(4) rimanente. Risultato: [1,1,2,3,4,4].
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeTwoLists(l1, l2):
dummy = ListNode(0)
curr = dummy
step = 0
while l1 and l2:
step += 1
if l1.val <= l2.val:
print(f'Step {step}: pick l1({l1.val})')
curr.next = l1; l1 = l1.next
else:
print(f'Step {step}: pick l2({l2.val})')
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
mergeTwoLists(build([1,2,4]),build([1,3,4]))Trovare il punto centrale con i puntatori lento e veloce
Per suddividere una lista in corrispondenza del punto centrale, utilizzi il modello dei puntatori lento e veloce. slow avanza di 1 passo, mentre fast avanza di 2 passi. Quando fast raggiunge None (o l'ultimo nodo), slow si trova nel punto centrale. Per una lista di lunghezza pari, questo metodo restituisce il primo dei due nodi centrali, come è convenzionale nella suddivisione per il merge sort.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def split_at_mid(head):
'''Returns (first_half_head, second_half_head).'''
slow, fast = head, head
while fast.next and fast.next.next:
slow = slow.next
fast = fast.next.next
mid = slow.next # second half starts here
slow.next = None # sever the list
return head, mid
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val); h=h.next
return r
head=build([1,2,3,4,5])
first, second = split_at_mid(head)
print(to_list(first), to_list(second)) # [1,2,3] [4,5]Merge sort su una lista concatenata
LeetCode 148 'Sort List': ordinare una lista concatenata in tempo O(n log n) e con spazio O(log n). L'approccio consiste nel dividere la lista a metà, ordinare ricorsivamente ciascuna metà e unirle. Il merge sort su una lista concatenata è naturale perché dividere la lista a metà richiede O(n) (non O(1) come per gli array), ma la complessità complessiva resta O(n log n), usando solo O(log n) di spazio nello stack.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def sortList(head):
if not head or not head.next:
return head
# Split
slow, fast = head, head.next
while fast and fast.next:
slow = slow.next
fast = fast.next.next
mid = slow.next
slow.next = None
# Recurse
left = sortList(head)
right = sortList(mid)
# Merge
dummy = ListNode(0)
curr = dummy
while left and right:
if left.val <= right.val:
curr.next = left; left = left.next
else:
curr.next = right; right = right.next
curr = curr.next
curr.next = left or right
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(sortList(build([4,2,1,3])))) # [1,2,3,4]Trovare l'n-esimo nodo dalla fine
LeetCode 19 'Remove Nth Node From End of List': trovare l'n-esimo nodo dalla fine in un'unica scansione. Si usano due puntatori separati esattamente da n nodi. Si fa avanzare fast di n passi rispetto a slow. Poi si fanno avanzare entrambi insieme finché fast raggiunge l'ultimo nodo. A quel punto slow si trova sul nodo (n+1)-esimo dalla fine, cioè sul predecessore del nodo da rimuovere.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def removeNthFromEnd(head, n):
dummy = ListNode(0, head)
fast = dummy
for _ in range(n + 1): # advance fast n+1 steps
fast = fast.next
slow = dummy
while fast: # advance both until fast is None
slow = slow.next
fast = fast.next
slow.next = slow.next.next # remove nth node
return dummy.next
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(removeNthFromEnd(build([1,2,3,4,5]), 2))) # [1,2,3,5]Perché n+1 passi nella rimozione dell'n-esimo nodo
La sottigliezza fondamentale consiste nel far avanzare fast di n+1 passi (non n) a partire dal nodo fittizio. Dopo n+1 passi, fast si trova n+1 posizioni avanti rispetto a slow (entrambi partono dal nodo fittizio). Quando fast raggiunge None (una posizione oltre la coda), slow si trova n+1 posizioni prima di None: ciò significa che è in posizione (length - n - 1) contando da zero, cioè sul predecessore del nodo cercato. In questo modo, slow.next = slow.next.next elimina in modo semplice il nodo n-esimo dalla fine.
# Visual: list = [1,2,3,4,5], n=2
# dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> None
# After n+1=3 forward steps from dummy, fast=3
# dummy(slow) 1 2 3(fast) 4 5 None
# Advance both until fast=None:
# Step 1: slow=1, fast=4
# Step 2: slow=2, fast=5
# Step 3: slow=3, fast=None
# slow is at 3, slow.next=4 (the 2nd from end) -> delete
print('slow.next (to delete): 4')
print('Result: [1, 2, 3, 5]')Intersezione di due liste concatenate
LeetCode 160 'Intersection of Two Linked Lists': trovare il nodo in cui due liste si intersecano per la prima volta. Il trucco con spazio O(1) consiste nel far avanzare due puntatori, uno per lista. Quando un puntatore raggiunge None, lo si reindirizza alla testa dell'altra lista. Dopo al massimo len(A) + len(B) passi, entrambi i puntatori hanno percorso la stessa distanza complessiva e devono trovarsi sul nodo di intersezione (oppure entrambi su None se non esiste alcuna intersezione).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def getIntersectionNode(headA, headB):
a, b = headA, headB
while a is not b:
a = a.next if a else headB
b = b.next if b else headA
return a # None if no intersection
# Build: A: 4->1->\ B: 5->6->1->\ both -> 8->4->5
shared = [ListNode(v) for v in [8, 4, 5]]
shared[0].next = shared[1]; shared[1].next = shared[2]
A = ListNode(4); A.next = ListNode(1); A.next.next = shared[0]
B = ListNode(5); B.next = ListNode(6); B.next.next = ListNode(1); B.next.next.next = shared[0]
print(getIntersectionNode(A, B).val) # 8Unire K liste ordinate (divide et impera)
LeetCode 23 'Merge K Sorted Lists': date k liste ordinate, unirle in una sola. L'approccio ottimale consiste nell'unire ripetutamente coppie di liste usando divide et impera, dimezzando il numero di liste a ogni passaggio. Con k liste di lunghezza media n, sono necessari O(n k log k) passi, rispetto a O(n k²) per l'unione sequenziale. Anche un approccio basato su un min-heap richiede O(n k log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def mergeKLists(lists):
def merge_two(l1, l2):
dummy = ListNode(0); curr = dummy
while l1 and l2:
if l1.val <= l2.val:
curr.next = l1; l1 = l1.next
else:
curr.next = l2; l2 = l2.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
if not lists: return None
while len(lists) > 1:
merged = []
for i in range(0, len(lists), 2):
l1 = lists[i]
l2 = lists[i+1] if i+1 < len(lists) else None
merged.append(merge_two(l1, l2))
lists = merged
return lists[0]
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
lists=[build([1,4,5]),build([1,3,4]),build([2,6])]
print(to_list(mergeKLists(lists))) # [1,1,2,3,4,4,5,6]Lista concatenata con indici dispari e pari
LeetCode 328 'Odd Even Linked List': raggruppare prima tutti i nodi con indice dispari, poi quelli con indice pari (con indicizzazione a partire da 1). L'approccio consiste nel mantenere due catene separate (dispari e pari) e collegarle al termine. È sufficiente un'unica scansione della lista, con complessità O(n) e spazio O(1). Questo è un esempio chiaro di avanzamento simultaneo di due puntatori con passi diversi.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def oddEvenList(head):
if not head:
return head
odd = head
even = head.next
even_head = even
while even and even.next:
odd.next = even.next
odd = odd.next
even.next = odd.next
even = even.next
odd.next = even_head
return head
def build(arr):
d=ListNode();c=d
for v in arr: c.next=ListNode(v);c=c.next
return d.next
def to_list(h):
r=[]
while h: r.append(h.val);h=h.next
return r
print(to_list(oddEvenList(build([1,2,3,4,5])))) # [1,3,5,2,4]Riunire tutti i concetti
I tre schemi di questa lezione — unire liste ordinate, dividere a metà e trovare l'n-esimo nodo dalla fine — condividono un tema comune: usare variabili aggiuntive per i puntatori, così da tenere traccia delle posizioni senza memoria aggiuntiva. La testa fittizia semplifica l'unione e l'eliminazione; la distanza tra slow e fast fissa una posizione relativa specifica; far avanzare prima un puntatore crea la separazione desiderata.
Durante un colloquio tecnico, nomini lo schema che sta usando prima di scrivere il codice: 'Userò la tecnica dei due puntatori separati da una distanza per trovare l'n-esimo nodo dalla fine in un'unica scansione.' In questo modo dimostra di ragionare in maniera strutturata.
Verifica rapida
Verifichi la propria comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep presentati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: unire due liste ordinate richiede una testa fittizia e un confronto a ogni passaggio, con complessità O(n+m) e spazio O(1), dividere a metà richiede puntatori slow-fast, con fast che si arresta sull'ultima coppia valida e trovare l'n-esimo nodo dalla fine richiede di far avanzare fast di n+1 passi, in modo che slow finisca sul predecessore. Ora costruiremo stack e code e li applicheremo a classici problemi da colloquio tecnico.
Domande Frequenti
La lezione «Unire, dividere e trovare l'ennesimo elemento dalla fine» è gratuita?
Sì — il testo completo di «Unire, dividere e trovare l'ennesimo elemento dalla fine» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso Coding Interview Prep, passa a CoddyKit PRO. Il corso Coding Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Unire, dividere e trovare l'ennesimo elemento dalla fine»?
Unisca due liste concatenate ordinate in O(n), divida una lista a metà usando puntatori lento e veloce e trovi l'ennesimo nodo dalla coda Eserciti Coding Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare Coding Interview Prep?
Non è richiesta alcuna esperienza precedente. Coding Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Unire, dividere e trovare l'ennesimo elemento dalla fine»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione Coding Interview Prep?
Sì. Ogni lezione Coding Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Classe Node e costruzione delle liste
- Invertire una linked list
- Rilevamento dei cicli con l'algoritmo di Floyd
- Unire, dividere e trovare l'ennesimo elemento dalla fine