Given two sorted single linked lists list1,list2 write a algorithm to merge the two lists again in sorted order. No new nodes should be created.- Also give all the test cases for testing this algorithm

Interview Candidate
Oct 12th, 2006
6
2445

Showing Answers 1 - 6 of 6 Answers

brave

Dec 18th, 2006

L1= Array (1,3,7,9,11) ; L2 = Array (2,4,6,8,12,14);L3 = Array();
i=0;j=0;k=0;
while ( !(EOF(L1)) && !(EOF(L2)))
{
if L1[i]<L2[j] {L3[k] = L1[i];i++;}
else {L3[k]=L2[j];j++;}
k++;
}
for (i=0;i<=k;i++)
print_r(L3[i]);

Udit Agarwal
Profile Answers by Udit Agarwal

Dec 10th, 2010

ASSUMPTIONS: 'list' is a class with 'head' as it's public data member and 'getlist()' & 'print()' as it's member functions .
in 'struct node' a constructor node() is also used.

node* merge(list l1, list l2)
{
   node* p =l1.head ;
   node* q= l2.head;
   node* r= NULL ;
   node* tmp;
   while (p != NULL && q != NULL)
   {
   if (p->a < q->a )
   {
   tmp = p->next ;
   p->next = q;
   if (r != NULL)
   {
   r->next = p;
   }
   r = p;
   p = tmp;
   }
   else
   {
   if (r == NULL)
   l1.head = q;
   tmp = q->next;
   q->next = p;
   if (r != NULL)
   {
   r->next = q;
   }
   r = q;

   q = tmp;
   }
   }
   l1.print();
}