题目：
我们提供的服务有：成都网站制作、网站建设、外贸网站建设、微信公众号开发、网站优化、网站认证、称多ssl等。为上1000+企事业单位解决了网站和推广的问题。提供周到的售前咨询和贴心的售后服务，是有科学管理、有技术的称多网站制作公司
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路1：让两个指针分别指向两个链表，谁小就将当前节点尾插入新链表中
代码：
/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1==NULL)
{
return pHead2;
}
else if(pHead2==NULL)
{
return pHead1；
}
//两个指针
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;
}
return newhead;
}
};思路二：通过递归，每次找出最小的元素，加入到新的链表的后面
代码：
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
//终止条件
if(pHead1==NULL)
{
return pHead2;
}
else if(pHead2==NULL)
{
return pHead1;
}
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);
}
return newhead;
}
