两个有序链表合并

1.两个链表都带有头结点

Node* Merge(Node* head1, Node* head2)

{

　　if(head1==NULL || head1->next==NULL)

　　　　return head2;

　　if(head2==NULL || head2->next==NULL)

　　　　return head1;

　　Node* p1=NULL;

　　Node* p2=NULL;

　　Node* head=NULL;

　　//找出两个链表中第一个结点较小的结点，head记录较小结点的头结点

　　if(head1->next->data < head2->next->data)

　　{

　　　　head=head1;

　　　　p1=head1->next;

　　　　p2=head2->next;

　　}

　　else

　　{

　　　　head=head2;

　　　　p1=head2->next;

　　　　p2=head1->next;

　　}

　　//在两个链表中遍历比较，将值较小的结点链接到pCur结点后

　　Node* pCur=head;

　　while(p1!==NULL && p2!=NULL)

　　{

　　　　if(p1->data < p2->data)

　　　　{

　　　　　　pCur->next=p1;

　　　　　　pCur=p1;

　　　　　　p1=p1->next;

　　　　}

　　　　else

　　　　{

　　　　　　pCur->next=p2;

　　　　　　pCur=p2;

　　　　　　p2=p2->next;

　　　　}

　　}

　　//将p1或p2剩余的结点链到pCur之后，完成整个合并的过程

　　if(p1!=NULL)

　　　　pCur->next=p1;

　　if(p2!=NULL)

　　　　pCur->next=p2;

　　return head;

}

两个有序链表合并

原文：http://www.cnblogs.com/hj-blog/p/4430836.html