Inversarea listei înlănțuite pierde noduri (curent.urm suprascris înainte de avans)
Ai schimbat curent.urm = anterior înainte să salvezi următorul nod, iar apoi curent = curent.urm te duce înapoi, nu înainte. Salvează întâi urmator = curent.urm, abia apoi întoarce legătura și avansează cu curent = urmator.
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Inversarea pe loc a unei liste înlănțuite folosește trei referințe: anterior, curent și urmator. La fiecare pas întorci legătura nodului curent spre cel anterior. Problema e ordinea: imediat ce scrii curent.urm = anterior, ai pierdut singura referință spre restul listei. Dacă avansezi apoi cu curent = curent.urm, ajungi la anterior, nu la următorul nod.
Nu primești nicio eroare. În varianta tipică, bucla se oprește după primul nod și lista inversată are un singur element, iar restul nodurilor sunt pierdute. În alte ordini greșite poți obține o buclă infinită (nodurile ajung să se arate unul pe altul).
Desenează pe hârtie trei căsuțe și săgețile la fiecare pas: ajută mai mult decât orice explicație.
De ce apare: cauzele frecvente
1Avansul se face după ce legătura a fost întoarsă
anterior, curent = None, cap
while curent:
curent.urm = anterior
anterior = curent
curent = curent.urmanterior, curent = None, cap
while curent:
urmator = curent.urm
curent.urm = anterior
anterior = curent
curent = urmatorurmator păstrează drumul spre restul listei înainte ca legătura să fie schimbată.
2Funcția returnează capul vechi
while curent:
...
return capwhile curent:
...
return anteriorDupă inversare, vechiul cap e ultimul nod. Noul cap e anterior, ultimul nod procesat.
3Atribuire multiplă în ordinea greșită
curent, curent.urm, anterior = curent.urm, anterior, curentcurent.urm, anterior, curent = anterior, curent, curent.urmPartea din dreapta se calculează întâi, dar atribuirile se fac de la stânga la dreapta. Dacă schimbi curent primul, curent.urm se referă deja la alt nod. Varianta cu urmator explicit e mai sigură.
Repară eroarea, direct în pagină
Funcția inverseaza(cap) inversează pe loc o listă înlănțuită de comenzi, dar testul cu assert pică: din lista inversată lipsesc noduri. Repar-o ca testele să treacă și să afișeze [3, 2, 1], [7] și [].
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def valori(cap):
rez = []
while cap:
rez.append(cap.val)
cap = cap.urm
return rez
def inverseaza(cap):
anterior, curent = None, cap
while curent:
curent.urm = anterior
anterior = curent
curent = curent.urm
return anterior
for cap, corect in [(Nod(1, Nod(2, Nod(3))), [3, 2, 1]), (Nod(7), [7]), (None, [])]:
rez = valori(inverseaza(cap))
assert rez == corect, f'lista gresita: {rez}'
print(rez)[3, 2, 1] [7] []
Indiciu
Salvează curent.urm într-o variabilă înainte să-l schimbi și avansează cu ea.
Reparația
class Nod:
def __init__(self, val, urm=None):
self.val = val
self.urm = urm
def valori(cap):
rez = []
while cap:
rez.append(cap.val)
cap = cap.urm
return rez
def inverseaza(cap):
anterior, curent = None, cap
while curent:
urmator = curent.urm
curent.urm = anterior
anterior = curent
curent = urmator
return anterior
for cap, corect in [(Nod(1, Nod(2, Nod(3))), [3, 2, 1]), (Nod(7), [7]), (None, [])]:
rez = valori(inverseaza(cap))
assert rez == corect, f'lista gresita: {rez}'
print(rez)De ce merge
La primul pas, curent.urm = anterior punea None în legătura nodului 1, iar curent = curent.urm citea chiar acel None: bucla se oprea și nodurile 2 și 3 erau pierdute. Cu urmator = curent.urm salvat înainte, legătura spre restul listei nu se mai pierde. Fiecare nod e vizitat o dată, deci inversarea e O(n) timp și O(1) memorie.
Alte forme ale mesajului
Programul a rulat prea mult și a fost oprit. Verifică dacă ai o buclă infinită.
Cum o eviți pe viitor
Când modifici legături, regula e: salvează ce urmează să pierzi, apoi schimbă. Scrie cei patru pași mereu în aceeași ordine (salvezi următorul, întorci legătura, muți anterior, muți curent). Testează pe liste de 0, 1, 2 și 3 noduri și afișează lista ca valori după fiecare operație, cu o funcție ajutătoare valori(cap).
Întrebări frecvente
Se poate inversa și recursiv?
Da: inversezi restul listei, apoi cap.urm.urm = cap și cap.urm = None. Dar adâncimea recursivității e egală cu lungimea listei, deci pe liste lungi primești RecursionError.
De ce nu am primit nicio eroare?
Pentru că toate operațiile sunt valide: legăturile sunt doar puse greșit. Python nu are de unde să știe ce listă voiai.
Erori înrudite
Parcurgerea listei înlănțuite nu se mai oprește (lipsește curent = curent.urm) În bucla while curent: ai uitat să avansezi cu curent = curent.urm (sau avansezi doar pe o ramură a unui if), așa că nodul curent nu se schimbă și bucla rulează la nesfârșit; editorul o oprește după limita de timp. Avansează pe fiecare drum prin buclă. AttributeError: 'NoneType' object has no attribute 'urm' Ai ajuns la capătul listei înlănțuite (nodul curent e None) și ai cerut încă .urm sau .val. Verifică nodul înainte de acces: while curent and curent.urm:, iar la doi pași (rapid.urm.urm) verifică ambii pași. nou = stare nu copiază lista: modifici „copia” și se schimbă și originalul nou = stare nu creează o listă nouă, ci un al doilea nume pentru aceeași listă. Orice modificare prin nou se vede și prin stare. Copiază explicit: nou = stare[:] sau list(stare), iar pentru liste de liste [r[:] for r in stare]. Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
