题目：
输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
思路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;
}亿速云「云服务器」，即开即用、新一代英特尔至强铂金CPU、三副本存储NVMe SSD云盘，价格低至29元/月。点击查看>>
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
