mardi 5 mai 2015

Reversing a linked list, head still points to original first element

I am trying to reverse a linked list using the following program. At the end head still points to the first element of the original list. Where am I making the mistake?

#include <iostream>

struct node{
    node(int val):
        value(val),
        next(nullptr)
    {}

    ~node(){
        delete next;
        std::cout << "Deleting " << value << std::endl;
    }

    int value;
    node* next;
};

node* create()
{
    node * head =  new node(1);
    head->next = new node(2);
    head->next->next = new node(3);
    head->next->next->next = new node(4);
    head->next->next->next->next = new node(5);
    return head;
}

void print(node* head)
{
    auto ptr = head;
    while(ptr !=nullptr)
    {
        std::cout <<  ptr->value << " -> " ;
        ptr = ptr->next;
    }
    std::cout << "nullptr" << std::endl;
}

void reverse(node** head_p)
{
    auto head = *head_p;

    auto p2 = head->next;
    head->next = nullptr;

    while(p2!=nullptr)
    {
        auto temp = head;
        head = p2;
        p2 = p2->next;
        head->next = temp;
    }
}

int main()
{
    auto head = create();
    print(head);

    reverse(&head);

    print(head);
    delete head;
    return 0;
}

Aucun commentaire:

Enregistrer un commentaire