The problem is just like merging step in merge sort, wherein we have two sorted arrays and merge them into one. If you haven’t already gone through the linked list concepts, I would recommend you to go through that first. The algorithm is simple and stated as:

struct node *merge(struct node *p,struct node *q)
{
struct node *r,*s;
struct node *a=NULL;
r=p; s=q;
while(r !=NULL && s!= NULL)
{
if(r->data <= s->data)
{
a=insert(a,r->data);
r=r->link;
}
else{
a=insert(a,s->data);
s=s->link;
}
}
if(r==NULL)
while(s!=NULL)
{
a=insert(a,s->data);
s=s->link;
}
else
while(r!=NULL)
{
a=insert(a,r->data);
r=r->link;
}
return a;
}

### Like this:

Like Loading...

*Related*

#1 by

Alexwebmasteron March 3, 2009 - 11:05 amHello webmaster

I would like to share with you a link to your site

write me here preonrelt@mail.ru

#2 by

vie90on June 20, 2009 - 2:46 pmthanks for all

#3 by

Kashifon January 27, 2011 - 6:38 pm// merges two Singly linked lists A and B, both sorted in increasing order of integers .

// Return a Singly linked list sorted in increasing order

// for ex if A = 1->2->3->6 and B = 2->4->7, returns 1->2->2->3->4->6->7

public LinkedList merge(LinkedList A, LinkedList B) {

Node 1A = A.head;

Node 1B = B.head;

Node P1A = NULL;

Node 2A = NULL;

Node 2B = NULL;

while ( 1A != NULL && 1B !=NULL){

2A = 1A.next;

2B = 1B.next;

if (1A.item >= 1B.item) {

if (P1A != NULL) {

P1A.next = 1B;

}

else if ( P1A == NULL){

P1A = 1B;

}

1B.next = 1A;

P1A = 1B;

1B = 2B;

}

else if ( 1A.item < 1B.item){

if ( 2A != NULL) {

P1A = 1A;

1A = 1A.next;

}

else{

1A.next = 1B;

break;

}

}

}

return A;

}