题目：

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路1：让两个指针分别指向两个链表，谁小就将当前节点尾插入新链表中

代码：

/*structListNode{intval;structListNode*next;ListNode(intx):val(x),next(NULL){}};*/classSolution{public:ListNode*Merge(ListNode*pHead1,ListNode*pHead2){if(pHead1==NULL){returnpHead2;}elseif(pHead2==NULL){returnpHead1；}//两个指针ListNode*newhead=NULL;ListNode*cur=NULL;ListNode*p1=pHead1;ListNode*p2=pHead2;ListNode*temp=NULL;//注意，如果是如下这种写法：有一个很大的漏洞//看起来newhead的next是cur//但是当找到第二个数的时候，cur就指向别处//newhead所在链表只有一个节点/*while(p1!=NULL&&p2!=NULL){if(p1->_data<=p2->_data){cur=p1;p1=p1->_next;}else{cur=p2;p2=p2->_next;}if(newhead==NULL){newhead=cur;}cur->_next=NULL;cur=cur->_next;}*/while(p1!=NULL&&p2!=NULL){if(p1->val<=p2->val){temp=p1;p1=p1->next;}else{temp=p2;p2=p2->next;}if(newhead==NULL){newhead=temp;cur=newhead;}else{cur->next=temp;cur=cur->next;}}if(p1!=NULL){cur->next=p1;}else{cur->next=p2;}returnnewhead;}};

思路二：通过递归，每次找出最小的元素，加入到新的链表的后面

代码：

ListNode*Merge(ListNode*pHead1,ListNode*pHead2){//终止条件if(pHead1==NULL){returnpHead2;}elseif(pHead2==NULL){returnpHead1;}ListNode*newhead=NULL;if(pHead1->val<=pHead2->val){newhead=pHead1;newhead->next=Merge(pHead1->next,pHead2);}else{newhead=pHead2;newhead->next=Merge(pHead1,pHead2->next);}returnnewhead;}