[C++] odwrócenie listy jednokierunowej

[anilahcim]

Próbuję napisać funkcję, która odwróci listę. Ostatni element przechodzi mi na pierwszą pozycję, ale reszta się nie zmienia - proszę o pomoc w znalezieniu błędu w kodzie.

Kod: Zaznacz cały

void odwroc_glowe (wezel*& glowa)
{
    if (glowa==NULL || glowa->nast==NULL)
        return;

    else
    {
        wezel* koniec = glowa;
        while (koniec->nast!=NULL)
            koniec=koniec->nast;
        wezel* w = koniec;
        
        do
        {
            w->nast=glowa;
            glowa=glowa->nast;
            w=w->nast;
            w->nast=NULL;
        }
        while (glowa!=koniec);
    }
}

A to cały kod:

Kod: Zaznacz cały

#include "funkcje.h"
#include <iostream>
#include <cassert>

using namespace std;


void dodaj_element(wezel*& glowa, double x, int i)
{
    wezel* w = new wezel;
    w->wartosc=x;

    if(i==0)
    {
        w->nast=glowa;
        glowa=w;
    }

    else
    {
        wezel* w2; 
        w2 = glowa;
        while (i>1)
        {
            w2=w2->nast;
            i--;
        }
        w->nast=w2->nast;
        w2->nast=w;
    }
}


void wypisz_liste (wezel* glowa)
{
    while (glowa!=NULL)
    {
        cout<<glowa->wartosc<<endl;
        glowa=glowa->nast;
    }
}

void odwroc_glowe (wezel*& glowa)
{
    if (glowa==NULL || glowa->nast==NULL)
        return;

    else
    {
        wezel* koniec = glowa;
        while (koniec->nast!=NULL)
            koniec=koniec->nast;
        wezel* w = koniec;
        
        do
        {
            w->nast=glowa;
            glowa=glowa->nast;
            w=w->nast;
            w->nast=NULL;
        }
        while (glowa!=koniec);
    }
}

MAIN:

Kod: Zaznacz cały

#include "funkcje.h"
#include <iostream>
#include <cassert>

using namespace std;

int main()
{
    wezel* w = NULL;

    dodaj_element(w,7,0);
    dodaj_element(w,4,1);
    dodaj_element(w,5,2);
    dodaj_element(w,3,3);
    dodaj_element(w,0,4);

    wypisz_liste(w);

    odwroc_glowe(w);
    wypisz_liste(w);

    system ("pause");
    return 0;
}

[royas]

To nie jest błąd w kodzie lecz jakby w całym algorytmie. Po prostu jakby przewijasz całą kolejkę.
Myślę, że może się to opierać o takie coś P,A,N wskazują na 3 kolejne elementy listy (na początku P=null; A=glowa)

Kod: Zaznacz cały

A->N=P;
P=A;
A=N;
N=A->N;

[anilahcim]

Próbowałam jakoś to zrozumieć rysując sobie, ale muszę źle rysować, bo na moim rysunku jest co innego, niż dzieje się w programie.

Znalazłam taki kod (wydaje mi się, że działa to tak, jak napisał royas):

Kod: Zaznacz cały

void OdwracanieListy(Wezel *&poczatek) 
{ Wezel * nowyPoczatek = NULL; 
  Wezel *tmp; 
  while(poczatek != NULL) 
     { tmp = poczatek->nastepny; 
       poczatek->nastepny = nowyPoczatek; 
       nowyPoczatek = poczatek; 
       poczatek = tmp;  
     } 
poczatek = nowyPoczatek; 
}

Wszystko działa, ale ciągle nie mogę zrozumieć jak... Byłabym wdzięczna, jeśli ktoś mógłby mi to rozrysować albo spróbować jakoś wytłumaczyć.

[royas]

Masz trzy wskaźniki robocze, wskazujące na trzy kolejne elementy listy.
W każdym kroku modyfikujesz wskaźnik next w środkowym elemencie tak aby wzkazywał na swojego dotychczasowego poprzednika. Przykład kolejnych kroków:

Kod: Zaznacz cały

a->b->c->d->null
null<-a  b->c->d->null
null<-a<-b  c->d->null
null<-a<-b<-c  d->null
null<-a<-b<-c<-d