Rezolvare PBinfo #3801

Se consideră o listă liniară simplu înlănțuită, alocată dinamic, în care elementele sunt de tipul declarat mai jos:

struct Nod
{
    int info;
    Nod *leg;
};

Câmpul info memorează un număr întreg, iar câmpul leg memorează adresa următorului element al listei.

Cerinţa

Se dau două liste în care informațiile sunt ordonate crescător. Adresele celor două liste sunt memorate în pointerii h1 și h2. Să se scrie o funcție C++ cu următorul antet:

void LsiInterclasare(Nod *h1, Nod *h2, Nod *&h)

care interclasează nodurile într-o nouă listă de adresă h și care are de asemenea informațiile ordonate crescător. Atenție la faptul că nu puteți să ștergeți și să creați noi noduri, ci numai să schimbați legăturile nodurilor. Dacă există noduri de informație identică în ambele liste, mai întâi se va depune în h nodul din h1.

Restricţii şi precizări

• cele două liste inițiale conțin fiecare cel puțin un nod
• la ieșirea din apel h va memora adresa primului element al listei interclasate

Exemplu:

Dacă h1 = 2,7,7,10,20 și h2 = 1,1,7,9,20,25,30, atunci după apelul funcției h = 1,1,2,7,7,7,9,10,20,20,25,30. Rețineți că mai întâi s-au depus în h nodurile de informație 7 din prima listă, apoi din a doua.

Important

Soluţia propusă va conţine definiţia funcţiei cerute. Prezenţa în soluţie a altor instrucţiuni poate duce erori de compilare sau de execuţie care vor avea ca efect depunctarea soluţiei.