【答案解析】合并两个有序链表(假设链表元素为升序排列)，一般可以采用递归和非递归两种方式实现。
首先看递归方式，设两个链表的头结点分别为head1、head2，如果head1为空，则直接返回head2；如果head2为空，则直接head1。如果headl链表的第一个数据小于head2链表的第一个数据，则把head1链表的第一个元素存储到新合并的链表中，递归遍历去除第一个元素的head1链表和整个head2链表。如果head1链表的第一个元素大于或等于head2链表的第一个元素，则把head2链表的第一个元素存储到新合并的链表中，递归遍历整个head1链表，去除第一个元素的head2链表。具体过程如下：
Node * MergeRecursive(Node *head1, Node *head2)
{
if(head1==NULL)
return head2;
if(head2==NULL)
return head1;
Node *head=NULL;
if(head1-＞data＜head2-＞data)
{
head=head1;
head-＞next=MergeRecursive(head1-＞next,head2);
}
else
{
head=head2;
head-＞next=MergeRecursive(head1,head2-＞next);
}
return head;
}
使用非递归的方式时，分别用指针head1、head2来遍历两个链表，如果当前head1指向的数据小于head2指向的数据，则将head1指向的结点归入合并后的链表中；否则将head2指向的结点归入合并后的链表中。如果有一个链表遍历结束，则把未结束的链表连接到合并后的链表尾部。具体过程如下：
Node* Merge(Node *head,Node *head1,Node *head2)
{
Node *trap=head;
while(NULL!=head1 && NULL!=head2)
{
if(head1-＞data＜head2-＞data)
{
tmp-＞next=head1;
tmp=head1;
head1=head1-＞next;
}
else
{
tmp-＞next=head2;
tmp=head2;
head2=head2-＞next;
}
}
if(NULL!=head1)
{
tmp-＞next=head1;
}
if(NULL!=head2)
{
tmp-＞next=head2;
}
return tmp;