Inversarea unei liste simplu înlănțuite

Cum inversezi o lista simplu inlantuita?

Aceasta este o problemă destul de des întălnită la interviurile de angajare la diverste companii. La prima vedere nu pare o problemă foarte grea, dar pe măsura ce începeți să vă gândiți la o posibilă rezolvare vă înpotmoliți tot mai mult. Iată enunțul problemei:

Scrie o funcție care primesțe o listă simplu înlănțuită și o inversează pe loc, fără a crea o altă listă și întoarce noul cap al listei. Puteți presupune că lista primită va avea cel puțin un nod, cu alte cuvinte capul listei nu va fi niciodată NULL.

Cum rezolvăm problema?

Un mic sfat pentru început este să facem abstracție de cazurile limită și să vedem ce ar trebui să facem ca să inversăm un singur nod. Astfel vom vedea ce avem de făcut pentru restul nodurilor. Așadar o să punem un pointer P către un nod (ne imaginăm ca avem acces la el) și o să vedem ce ar trebui să facem mai departe:

#include    <iostream>

using namespace std;

struct Nod
{
    int numar;      // Memorarea efectiva a numarului
    Nod* next;      // Memorarea legaturii catre urmatorul nod
};

void inserareInceput(Nod* &cap, int valoare)
{
    Nod *elem = new Nod; //Creeam noul nod si ii atribuim valoarea din paramentru
    elem->numar = valoare;
    elem->next = cap; //Mutam sageata catre primul element din lista

    cap = elem; // Inlocuim primul element din lista
}

void afisareLista(Nod* cap)
{
    while (cap != NULL)
    {
        cout << cap->numar << "\n"; // Afisam numarul stocat
        cap = cap->next;            // Mutam elementul curent la urmatorul element din lista
    }
}

int main()
{
    Nod* cap = NULL;    // Declararea listei vida
    
    inserareInceput(cap, 11);
    inserareInceput(cap, 92);
    inserareInceput(cap, 24);
    inserareInceput(cap, 12);
    
    afisareLista(cap);
    return 0;
}

Citirea și afișarea preluate din: Liste simplu inlantuite – Structuri de date alocate dinamic

Declararea unui pointer pre

Am ales nodul cu numărul 24. Observăm că putem accesa nodul cu numărul 92 folosing P.next. Dat fiind faptul că lista este doar simplu înlănțuită nu avem o proprietate anume care să ne lase să accesăm nodul precedent. De aici tragem concluzia că mai avem nevoie de un pointer previous. Având acces la elementul precedent, putem să folosim o operație simplă. Pentru a face ca următorul nod după 24 să fie 12 vom face:

p.next = pre;

Declararea unui pointer urm

Există însă o mică problemă. Făcând această operație, nu mai avem acces la nodul cu numărul 92 deoacere p.next ne duce către nodul cu numărul 12. Cum remediem această problemă? Foarte simplu. Mai declarăm un pointer urm. Astfel vom avea următorul desen:

Deja am rezolvat 50% din problemă. Restul problemei constă în ce facem de aici încolo. De aici va trebui să mutăm cei 3 pointeri cu o poziție mai la dreapta. Cheia este să avem grijă in ce ordine vom face asta ca să nu pierdem legături. Mai întăi vom stoca pointerul p în pointerul pre, apoi pointerul urm în pointerul pre.

Algoritmul pentru inversarea unei liste simplu înlănțuite

De aici vom face exact aceleași operații până la sfârșitul listei. Simplu, nu? De obicei lumea consideră această problemă dificilă fiindcă au nevoie de 3 pointeri pentru a o rezolva. Este destul de ciudat să te gândești că îți trebuie 3, dar asta este soluția.

Inițial vom declara pointerul previous cu NULL, P cu capul listei, iar next va fi declarat într-un while-loop. Acest while-loop se va termina când pointerul P ajunge la NULL. Iată sursa codului:

Nod* inverseazaLista(Nod* cap)
{
    Nod* pre = NULL;
    Nod* p = cap;
    while(p != NULL)
    {
        Nod* urm = p->next;
        p->next = pre;
        pre = p;
        p = urm;
    }
    return pre;
}