Reverse a linked list–Using Recursion

 

Introduction

   To test both data structure and the recursion concept, a wonderful and confusing interview question asked to experienced people is “Reverse a linked list using recursion without using extra space”.

The fun here is, we have to first understand the sequential concept to understand recursive. But if you understand sequential and do recursive based on it, you will be nowhere near to the correct solution.

  As recursion uses stack to store the arguments, we must decide what to store in the stack on each call to get the right linking done.

Concept

   In recursive approach, we need to move to the end of the node. But we must stop just before the end of the node, and we should have total 3 nodes in hand.

head (stack)                             head->next (not null)                head->next->next

head is what is in the stack. head->next->next will always be NULL. If it is not NULL, recursion continues. This is the base condition for our recursion.

if(!(head && head->next))

recur(head->next);

if head and head->next, both are not NULL.. don’t return. Recursion goes on until we get the last two nodes. but note that, in last recursion where we return, we will have something like this,

                                                     head                                    head->next 

here, head->next->next is NULL and the recursion returns since we are in the above situation.

now, we connect head->next->next to head. and set head->next to NULL. since, we have pushed the traversed head’s in the stack. In the next return, we will get,

              head  =>   head->next                           NULL <= result->next <= result

Note the change in the above address field location. Now, we have created two lists, one in reverse and un-reversed in forward direction. The important properties of these two lists and also loop invariants are,

• The reverse direction list always ends with NULL.
• The forward direction list always ends with the last node of the reversed list

This is why, we always get head->next->next as NULL. Which we again point it to head.

In this recursion, we have backed up root of the reversed list as return value. head->next as the argument and we always do head->next->next to make sure that, we get a valid 3 element entry.

Code

List* recur_rlist(List* head)

{

    List* result;

    if(!(head && head->next)) 

        return head;

    result = recur_rlist(head->next);

    head->next->next = head;

    head->next = NULL;

    return result;

}

void printList(List* head)

{

    while(head != NULL) {

        std::cout<<head->data<<" ";

        head = head->next;

    }

}

void main()

{

    List* list = createNode(2);

    append(list, createNode(3));

    append(list, createNode(4));

    append(list, createNode(5));

    append(list, createNode(6));

    List* revlist = recur_rlist(list);

    printList(revlist);

}

Important notes:

• Thanks to code snippet present in: http://www.daniweb.com/software-development/c/code/216620
• The major confusion comes in this because, we see the list from the reverse rather than from the forward as we do in a non-recursive routine
• After that confusion is solved, we need to make sure what is stored in the stack and what is returned?
• Note that ONLY THE ARGUMENT IS STORED IN THE STACK. So, we must be very careful in deciding what to store on the stack
• Note that, the head stored as argument in further recursion will always have head->next and head->next->next as valid pointers. This is made sure by the recursions base condition.
• If there is only one node, there is no need to reverse the list. So, its ok to check for head and head next both being non-NULL are not. If any one of it becomes NULL, we can blindly return the head recorded.
• reverse list always has the last node next set to NULL. So, from the forward list, we pop the last node part of the recursion and simple insert into head->next->next which pushes the last node of forward list into backward list
• The same approach if needs to be done without recursion requires a stack :)