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
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