输入两个递增排序的链表，合并这两个链表并使新链表中的结点仍然是按照递增排序的。


要合并两个递增的链表，首先找出两个链表的头结点中较小的一个就为合并后新链表的头结点，之后再依次将两个链表中的结点值进行相比较，依次将较小值在新链表中进行尾插，直到其中一个链表遍历完成，将剩余链表直接链在新链表的尾部就可以了，因为链表本来就是有序递增的；


程序设计如下：

#include<iostream>#include<assert.h>usingnamespacestd;template<classT>structListNode//链表结点结构{T_data;ListNode<T>*_next;};template<classT>ListNode<T>*buy_node(Tdata)//创建一个链表结点{ListNode<T>*tmp=newListNode<T>;tmp->_data=data;tmp->_next=NULL;returntmp;}template<classT>voidinit_list(ListNode<T>**node,Tdata)//初始化链表{*node=buy_node(data);}template<classT>voidpush_node(ListNode<T>*&head,Tdata)//插入链表结点{if(head==NULL){init_list(&head,data);return;}ListNode<T>*tmp=head;while(tmp->_next!=NULL){tmp=tmp->_next;}tmp->_next=buy_node(data);}template<classT>voidprint_list(ListNode<T>*head)//打印链表{while(head!=NULL){cout<<head->_data<<"->";head=head->_next;}cout<<"NULL"<<endl;}template<classT>voiddestroy_list(ListNode<T>*&head)//销毁链表{if(head!=NULL){ListNode<T>*cur=head;ListNode<T>*tmp=head;while(cur!=NULL){tmp=cur;cur=cur->_next;deletetmp;}head=NULL;}}//实现1：循环template<classT>ListNode<T>*MergeList(ListNode<T>*list1,ListNode<T>*list2){if(list1==NULL)//条件判断returnlist2;elseif(list2==NULL)returnlist1;ListNode<T>*newHead=NULL;ListNode<T>*tmp1=NULL;ListNode<T>*tmp2=NULL;if(list1->_data<=list2->_data)//决定新链表的头结点{newHead=list1;tmp1=list1->_next;tmp2=list2;}else{newHead=list2;tmp1=list1;tmp2=list2->_next;}ListNode<T>*cur=newHead;while((tmp1!=NULL)&&(tmp2!=NULL)){if(tmp1->_data<=tmp2->_data)//将较小值进行尾插{cur->_next=tmp1;cur=cur->_next;tmp1=tmp1->_next;}else{cur->_next=tmp2;cur=cur->_next;tmp2=tmp2->_next;}}if(tmp1==NULL)//将剩下的链表直接接在新链表后面cur->_next=tmp2;elsecur->_next=tmp1;returnnewHead;}//实现2：递归template<classT>ListNode<T>*MergeList(ListNode<T>*list1,ListNode<T>*list2){if(list1==NULL)//条件判断returnlist2;elseif(list2==NULL)returnlist1;ListNode<T>*newHead=NULL;if(list1->_data<=list2->_data){newHead=list1;newHead->_next=MergeList(list1->_next,list2);}else{newHead=list2;newHead->_next=MergeList(list1,list2->_next);}returnnewHead;}intmain(){ListNode<int>*list1=NULL;push_node(list1,1);push_node(list1,2);push_node(list1,3);push_node(list1,8);push_node(list1,11);push_node(list1,14);ListNode<int>*list2=NULL;push_node(list2,5);push_node(list2,6);push_node(list2,7);push_node(list2,8);push_node(list2,9);cout<<"list1:";print_list(list1);cout<<"list2:";print_list(list2);ListNode<int>*newhead=MergeList(list1,list2);cout<<"mergelist:";print_list(newhead);destroy_list(list1);destroy_list(list2);return0;}


运行程序：


从上面程序可以看出来，用递归比循环看起来更好理解和简洁。



《完》