参考资料：
[1]剑指OFFER课本 P145
关键词：
合并两个有序数列、插入新的节点、返回头节点、图解说明
图解说明:
merge.png
自己的答案：
/*
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 == nullptr)
return pHead2;
else if(pHead2 == nullptr)
return pHead1;
//思路可以参考:合并两个有序的序列
ListNode* MergeList = nullptr;
ListNode* MergeListHead = nullptr;
ListNode* pNode1 =pHead1;
ListNode* pNode2 =pHead2;
//步骤1：确定头节点
if(pNode1->val < pNode2->val)
{
MergeList = pNode1;
MergeListHead = MergeList;
pNode1 = pNode1->next;
}
else
{
MergeList = pNode2;
MergeListHead = MergeList;
pNode2 = pNode2->next;
}
//步骤2：两个非空就这样
while((pNode1 != nullptr) && (pNode2 != nullptr))
{
if(pNode1->val <=pNode2->val)
{
MergeList->next = pNode1;//这个涉及到如何添加节点的问题
MergeList = MergeList->next;
pNode1 = pNode1->next;
}
else
{
MergeList->next = pNode2;
MergeList = MergeList->next;
pNode2 = pNode2->next;
}
}
//步骤3：只要其中一个空了，就只弄其中一种
while(pNode1 != nullptr)
{
MergeList->next = pNode1;
MergeList = MergeList->next;
pNode1 = pNode1->next;
}
while(pNode2 != nullptr)
{
MergeList->next = pNode2;
MergeList = MergeList->next;
pNode2 = pNode2->next;
}
return MergeListHead;//返回头节点
}
};
下面这个答案更好。
标准答案：
/*
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 == nullptr)
return pHead2;
if(pHead2 == nullptr)
return pHead1;
//合并后的链表
ListNode* pMergeList;
//1.如果链表1的头结点的值小于链表2的头结点的值，那么链表1的头结点为合并后的头节点
if(pHead1->val <= pHead2->val)
{
pMergeList = pHead1;
pMergeList->next = Merge(pHead1->next,pHead2);
}
else if(pHead1->val > pHead2->val)
{
pMergeList = pHead2;
pMergeList->next = Merge(pHead1,pHead2->next);
}
//如果相等，怎么办？放在其中一个情况中即可
return pMergeList;
}
};
