CODEWITHSUNDEEP
crecursionlinked-list
raton
raton

Reputation: 428

reverse a linkedlist recursively

my linkedlist reverse function gives the correct result. but i am
confused. 

linked list= 12->5->4->3

as per my reverse function the result should be
4->5->12

but fortunately it produces the correct reversed list
3->4->5->12.

pls help me to understand what happening 




//head_ref  global variable



struct n* reverse(struct n *head){

    struct n *pre,*cur;  //temp variable for first and second node

    if(head->next==NULL){
        head_ref = head;   // head_ref global variable initialized with head pointer
        return;
     }
    pre = head;
    cur = head->next;
    reverse(cur);

    cur->next = pre ;
    pre->next = NULL;

 }

first call pre = 12 cur = 5 second call pre = 5 cur = 4 3rd call pre = 4 cur = 3

   3->next = NULL //base condition fullfilled
   so it will exit ( 3rd call )

   reverse will start from 
   second call
      pre = 5
      cur = 4

my reversed linked list should be 4->5->12

but it produces 3->4->5->12 (correct reversed linked list)

why it gives the correct result. pls explain????

Upvotes: 0

Views: 87

Answers (2)

Flying disk
Flying disk

Reputation: 130

Let us start with linked list 12->5->4->3. When your main (or other calling function) calls the reverse function, head has the data 12. Following is the stack created after the forth call to the reverse function.

                 |                                           |
                 |___________________________________________|     gonna be
                 |__*head=3 *head->next=NULL__head_ref=3_____| => popped out
                 |__*head=4 pre=4 curr=3_____________________|   
                 |__*head=5 pre=5 cur=4______________________|
     main calls=>|__*head=12_pre=12 cur=5____________________|

As you said, you are already clear with the above figure. When we have head->next = NULL, the top-most entry in the stack gets popped out and the one with *head=4, pre=4 and curr=3 becomes the topmost entry in the stack. Then curr->prev evaluates to 3->next=4 and 4->next->NULL.

                 |                                                      |
                 |                                                      |
    popped out=> |______________________________________________________|
                 |__*head=4 pre=4 curr=3__(3->next)=4__(4->next)=NULL___|
                 |__*head=5 pre=5 cur=4_________________________________|
                 |__*head=12_pre=12 cur=5_______________________________|

Then entry with *head=4 pre=4 curr=3__(3->next)=4__(4->next)=NULL pops out and the same thing happens.

                 |                                                      |
                 |                                                      |
                 |                                                      |
    popped out=> |______________________________________________________|
                 |__*head=5 pre=5 cur=4____(4->next)=5___(5->next=NULL)_|
                 |__*head=12_pre=12 cur=5_______________________________|

In the remaining one entry you can see 12->next becomes NULL, so 12 now becomes the tail of the linked list. 

                 |                                                      |
                 |                                                      |
                 |                                                      |
                 |                                                      |
    popped out=> |______________________________________________________|
                 |__*head=12_pre=12 cur=5__(5->next)=12_(12->next)=NULL_| 


                 |                                                      |
                 |                                                      |
                 |                                                      |
                 |                                                      |
                 |                                                      |
    popped out=> |______________________________________________________|

Stack becomes empty and your final linked list has 3 as the head and 12 as the tail:3->4->5->12

Upvotes: 3

fghj
fghj

Reputation: 9394

3->next = NULL //base condition fullfilled so it will exit ( 3rd call )

reverse will start from second call pre = 5 cur = 4

No reverse start from here

call pre = 4 cur = 3

you call reverse(3) which do nothing, and you execute lines

cur->next = pre ;
pre->next = NULL;

where cur=3 and pre = 4, so you got 3->4

Upvotes: 2

Related Questions