CODEWITHSUNDEEP
crecursionsingly-linked-list
Aseem Dua
Aseem Dua

Reputation: 143

reverse linked list recursively - different function signature

There are many posts with probably with same question but the problem says it has to be done by 

 node* reverseList (node * lh)
                              {
                               if(lh==NULL)............ ;

                                else if (lh->next==NULL)...........;

                                else ...........;
                              }

the three blanks must be filled the first two are simply 

return NULL

and 

return lh

repectively

one way could be just to go down and reverse the pointers but in that case how can i keep the tail intact even after backtracking? is it possible at all?

Upvotes: 0

Views: 573

Answers (3)

subbupkb
subbupkb

Reputation: 49

Below is an API which does the reversal of a Single linked list, this one of the best algo that i have seen:

void iterative_reverse() 
{ 

    mynode *p, *q, *r; 

    if(head == (mynode *)0) 
    { return; 
    } 

    p = head; 
    q = p->next; 
    p->next = (mynode *)0; 

    while (q != (mynode *)0) 
    { 
        r = q->next; 
        q->next = p; 
        p = q; 
        q = r; 
    } 
    head = p; 
 }

Upvotes: 1

NicolasP
NicolasP

Reputation: 764

I think this answers it:

node *reverseList(node *lh)
{
    if (!lh) return NULL;
    else if (!lh->next) return lh;
    else {
        node *new_head = reverseList(lh->next);
        lh->next->next = lh;
        lh->next = NULL;
        return new_head;
    }
}

It returns the head of the reversed list, i.e. the tail of the original list.

head = reverse_list(head);

Upvotes: 2

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726849

The trick to solving recursive problems is to pretend that you are done already. To solve this homework by yourself, you need to answer three questions:

  • How do you reverse an empty list? (i.e. a list with lh set to NULL)?
  • How do you reverse a list with only one item?
  • If someone could reverse all items on the list except the initial one for you, where do you add the first item from the initial list to the pre-reversed "tail" portion of the list?

You answered the first two already: NULL and lh are the right answers. Now think of the third one:

else {
    node *reversedTail = reverseList(lh->next);
    ...
}

At this point, reversedTail contains pre-reversed tail of your list. All you need to do is set lh->next to NULL, add it to the back of the list that you are holding, and return reversedTail. The final code looks like this:

else {
    node *reversedTail = reverseList(lh->next);
    node *p = reversedTail; 
    while (p->next) p = p->next;
    p->next = lh;
    lh->next = NULL;
    return reversedTail;
}

Upvotes: 3

Related Questions