reverse link list using recursion

Question

I am trying to reverse a link list using recursion. I have written a function "reverse(node* ptr) for this I am getting output as 40 40 20 while i expect output to be 40 , 20 , 10. below is the code posted.

class list {
    //some code;

    void reverse()
    {
        node* temp = new node;
        temp =first;
        reverse(temp);
        temp =NULL;
        delete temp;
    }

    void reverse(node* ptr) {


        if(ptr->next != NULL)
        {
           ptr =ptr->next;
           reverse(ptr);
        }
        cout << ptr->data << endl;
    }
    // some code;
};

int main()
{
    list ll;
    ll.insert(18);
    ll.insert(20);
    ll.insert(40);
    ll.display();
    ll.reverse();
    return 0;
}

please suggest what I am doing wrong here.

Thanks

node* temp = new node; temp =first; causes memory leak, you allocate a new node, and then you "forget" about it lose its address [note that doesn't address your question, it's a different issue] — amit
– amit, Commented Sep 23, 2011 at 8:38

flight · Accepted Answer · 2011-09-23 08:34:54Z

1

Before even talking about the linked list, there is a major problem with your code:

void reverse()
{
    node* temp = new node;
    temp =first;
    reverse(temp);
    temp =NULL;
    delete temp;
}

You allocate space for a node and then change what it is pointing to, to first. This means the memory you allocated will be leaked. Not only that but you then set it to NULL and then try to free it. You can't free NULL!

I believe you simply meant:

void reverse()
{
    reverse(first);
}

Simple. On to the linked list:

if(ptr->next != NULL)
{
    ptr =ptr->next;
    reverse(ptr);
}

You set ptr to the next element so when reverse() returns it will be one element ahead. I believe you meant:

if(ptr->next != NULL)
{
    reverse(ptr->next);
}

answered Sep 23, 2011 at 8:34

flight

7,3024 gold badges26 silver badges31 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Ruchi Over a year ago

Ok... for the second I changed it : void reverse(node* ptr) { if (ptr->next != NULL) { reverse(ptr); } count << ptr->data << endl; } still I am getting same issue.

MAK · Accepted Answer · 2011-09-23 08:33:58Z

0

You should get rid of the line ptr =ptr->next;.

The main objective is to print all the nodes that come after the current node before printing value of the current node. So simply a call to reverse(ptr->next) followed by a cout<<ptr->data<<endl should suffice, since the first call takes care of all nodes after ptr. There is no need to advance the pointer as we want to print the current node at the end.

answered Sep 23, 2011 at 8:33

MAK

26.6k11 gold badges57 silver badges86 bronze badges

Collectives™ on Stack Overflow

reverse link list using recursion

2 Answers 2

1 Comment

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Related