CODEWITHSUNDEEP
c++c++11recursiondata-structureslinked-list
mihir
mihir

Reputation: 15

Whats the issue with my code for Linked List reversal Recursive Method?

I am trying to reverse linked list using recursion.When I display the list after reversing I only get the first element of the original list `

        void reve(node *a,node *b,node *c,node *h1)
       {
               if(c->next==NULL)
           {
               c->next=b;
               b->next=a;
                return ;
           }

           reve(a->next,b->next,c->next,h1);
           c->next=b;
           b->next=a;
           if(a==h1)
         {
            a->next=NULL;
         }

         return ;

      }`

Upvotes: 0

Views: 44

Answers (1)

molbdnilo
molbdnilo

Reputation: 66371

It's because your calling code still holds a pointer to the node that used to be first, but that node is last now.
(At least if the code actually works – it's difficult to keep track of all those parameters, and their relationship is as mysterious as their names.)

This is easier to implement if you return a pointer to the new head.
You also only need one (1) parameter.

Then you have three cases to handle:

  1. The empty list – just return the empty list;
  2. A singleton list – just return it;
  3. The general case.

You can solve the general case by first reversing the rest of the list, receiving the new head.

Then you need to make next of the "new last element" point to "this" node in order to make "this" node the next element of the reversed list.
This is easier than it sounds – the last node in the reversed list you got from the recursion is still this node's next node.
(Draw it on paper if it's unclear.)

Then you also need to make "this" node terminate the list by nulling its next.

Then return the "new head" you received from the recursion.

node* reverse(node* n)
{
    // Empty list:
    if (!n)
    {
        return nullptr;
    }
    // Singleton list:
    if (!n->next)
    {
        return n;
    }
    // General case:
    node* head = reverse(n->next); // Reverse the rest,
    n->next->next = n;             // Attach this node at the end,
    n->next = nullptr;             // Terminate the list,
    return head;                   // Done.
}

Upvotes: 2

Related Questions