...
Eroare Algoritmi și structuri de date · Stive, cozi și liste înlănțuite

Inversarea listei înlănțuite pierde noduri (curent.urm suprascris înainte de avans)

Pe scurt

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ă

Greșit
PYTHON
anterior, curent = None, cap
while curent:
    curent.urm = anterior
    anterior = curent
    curent = curent.urm
Corect
PYTHON
anterior, curent = None, cap
while curent:
    urmator = curent.urm
    curent.urm = anterior
    anterior = curent
    curent = urmator

urmator păstrează drumul spre restul listei înainte ca legătura să fie schimbată.

2Funcția returnează capul vechi

Greșit
PYTHON
while curent:
    ...
return cap
Corect
PYTHON
while curent:
    ...
return anterior

După inversare, vechiul cap e ultimul nod. Noul cap e anterior, ultimul nod procesat.

3Atribuire multiplă în ordinea greșită

Greșit
PYTHON
curent, curent.urm, anterior = curent.urm, anterior, curent
Corect
PYTHON
curent.urm, anterior, curent = anterior, curent, curent.urm

Partea 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ă tu

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 [].

Codul care dă eroarea
PYTHON
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)
După reparație, programul afișează
[3, 2, 1]
[7]
[]
Indiciu

Salvează curent.urm într-o variabilă înainte să-l schimbi și avansează cu ea.

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

← Toate erorile Algoritmi și structuri de date

Tudor Andrei Dumitrescu
Cine a explicat eroarea

Tudor Andrei Dumitrescu

Senior Software Developer · fondatorul Academiei Programatorilor

LinkedIn
  1. 2019 Junior JavaCognizant Softvision
  2. 2021 Mid JavaCognizant Softvision
  3. 2022 Team LeaderEndava
  4. 2023 Senior Software DeveloperUniCredit
  5. Acum Senior Software DeveloperHCLTech
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu
Certificat de formator autorizatMinisterul Muncii și Ministerul Educației · 2022
Certificat de absolvire Instructor / Preparator formare, Tudor Andrei Dumitrescu

Certificat de formator autorizat · Ministerul Muncii și Ministerul Educației · 2022

Din 2020 construiește Academia Programatorilor, iar din 2026 și JoburiIT.ro. Fiecare eroare de aici a fost reprodusă în editorul nostru: codul greșit chiar dă mesajul din titlu, iar reparația chiar funcționează.

Î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.