Sunday, July 6, 2014

Merging two sorted linked list

Question : Given two sorted linked lists,How to manage them into the third list in sorted order

Pseudo code :  These problem can be resolved with both an iterative method as well as recursive method. Through out my experience I always find solution with recursive difficult to understand so I will try and explain recursive method in better way.

Code :
struct node* Merge_list( struct node *a,struct node *b)
{
struct node *result = NULL;
if(a == NULL)
       {
 return b;
       }
if(b == NULL)
{
         return a;
        }

if(a->data <= b->data)
{
result = a;
result->link = Merge_list(a->link,b);
}
else
{
result = b;
result->link = Merge_list(a,b->link);
}

return result;
}

Understanding :  By seeing above code I know most of the people find it difficult to understand.But if you try to understand solution with diagram it is not much difficult also.

Ex:

Sorted Link list elements of a : 1 -> 3 ->7
Sorted Link list elements of b : 2 -> 4 ->5

For sake simplicity as per below diagram I have assigned static address.If you follow below two diagrams carefully you will notice that how final result holds the end result.

Result linked list is : 1 -> 2 -> 3 -> 4 ->5 ->7


Static Link List Node




Red line of code shows value assigned while return from recursive call








No comments:

Post a Comment