Microsoft Interview Question
Software Engineer / DevelopersThanks Rahul. Did u appeared in MBD one the last saturday? I will shortly put the answer.
In delhi. A friend of mine was asked the same question in interview the last saturday. Did u attended the test at Nehru Place office?
struct node* sortedMergeRecursive(struct node* a, struct node* b)
{
struct node* result = NULL;
if (a==NULL) return(b);
else if (b==NULL) return(a);
// Pick either a or b, and recur
if (a->data <= b->data)
{
result = a;
result->next = sortedMergeRecursive(a->next, b);
}
else
{
result = b;
result->next = sortedMergeRecursive(a, b->next);
}
return(result);
}
assumiong the given linked list are sorted its just use use the merge procedure to murge the linked lists :)
struct node *MergeLinkedlist(struct node *l1,struct node *l2)
{
struct node *temp;
struct node *head=NUll;
struct node *temp1=l1;
struct node *temp2=l2
while(temp1 && temp2)
{
if(temp1->info<=temp2->info)
{
if(!head)
{head=temp1;
temp=head;
temp1=temp1->next;
temp->next=NULL;
}
else
{
temp->next=temp1;
temp=temp1;
temp1=temp1->next;
temp->next=NULL;
}
}
else
{
if(!head)
{
head=temp2;
temp=temp2;
temp2=temp2->next;
temp->next=NULL;
}
else
{
temp->next=temp2;
temp=temp2;
temp2=temp2->next;
temp->next=NULL;
}
}
}
if(!temp1)
{
while(temp1)
{
if(!head)
{head=temp1;
temp=head;
temp1=temp1->next;
temp->next=NULL;
}
else
{
temp->next=temp1;
temp=temp1;
temp1=temp1->next;
temp->next=NULL;
}}
if(!temp2)
{
while(temp2)
{
if(!head)
{
head=temp2;
temp=temp2;
temp2=temp2->next;
temp->next=NULL;
}
else
{
temp->next=temp2;
temp=temp2;
temp2=temp2->next;
temp->next=NULL;
}
}
}
}
return head;
}
I don't feel good,Why Do Guys Directly give Code??There must be a decent discussion irrespective of toughness of a problem...Anyway we may apply basic idea like...Just reach @ End of the first link list and give pointer of the first node of the second link list to its Last node next part..Now we can traverse both the list via Single pointer. We can sort resultant link list..
I think it is about two sorted linked lists right...
- netappreject July 10, 2010