合并有序链表

 

node * merge(node * head1,node * head2)
{
if(head1->next==NULL)
return head2;
if(head2->next == NULL)
return head1;
node * head=new node;

head->next=NULL;
node *q=head;
node *p1 = head1->next;
node *p;
node *p2= head2->next;
while(p1!=NULL&&p2!=NULL)
{
if(p1->data<p2->data)
{
         p=p1->next;
 p1->next=NULL;
 q->next=p1;
 q=q->next;
 p1=p;
}
else
{
p=p2->next;
p2->next=NULL;
q->next=p2;
q=q->next;
p2=p;
}
}
if(p1!=NULL)
q->next=p1;
if(p2!=NULL)
q->next=p2;
return head;
}

先捉个比较链表中元素的大小，当一个中元素已经没有了时，将另一个链表加到新的链表的后面。