算法-合并两个排序的链表
算法-合并两个排序的链表
题目： 输入两个递增排序的链表，合并着两个链表并使新链表中的结点仍然是按照递增顺序的。例如输入的链表1和链表2如下，合并后的为链表3。链表的结点定义如下：
struct ListNode
{
int value;
ListNode *next;
};
解题思路： 首先可以确定的是，链表1和链表2本身就是递增的，所以合并的过程可以从链表1，2的头结点开始，先比较1，2的头结点中值的大小，将小的值的结点（比如为链表1头结点）作为合并后的链表（链表3）的头结点。随后可以考虑成链表1的从原链表第二个结点开始，再次重复上面的步骤，这样就变成了一个递归问题。
代码实现：
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == NULL)
return pHead2;
else if(pHead2 == NULL)
return pHead1;
ListNode* pMergedHead = NULL;
if(pHead1->value < pHead2->value)
{
pMergedHead = pHead1;
pMergedHead->next = Merge(pHead1->next, pHead2);
}
else
{
pMergedHead = pHead2;
pMergedHead->next = Merge(pHead1, pHead2->next);
}
return pMergedHead;
}测试例程：
#include<iostream>
using namespace std;
struct ListNode
{
int value;
ListNode *next;
};
void ShowList(ListNode* L);
void CreateList(ListNode * L,int n,int initial);
ListNode* Merge(ListNode* pHead1, ListNode* pHead2);
int main()
{
ListNode * L1 = new ListNode;
L1->next = nullptr;
ListNode * L2 = new ListNode;
L2->next = nullptr;
CreateList(L1,4,1);
CreateList(L2,4,2);
ShowList(L1);
ShowList(L2);
ListNode * L3 = Merge(L1,L2);
ShowList(L3);
getchar();
return 0;
}
void CreateList(ListNode * L,int n,int initial)
{
L->value = initial;//输入第一个结点的数据值
n--;
for (int i = 0; i < n; i++)
{
initial = initial+2;
ListNode * p = new ListNode;
p->value = initial;
p->next = nullptr;
L->next = p;
L = p;
}
}
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == NULL)
return pHead2;
else if(pHead2 == NULL)
return pHead1;
ListNode* pMergedHead = NULL;
if(pHead1->value < pHead2->value)
{
pMergedHead = pHead1;
pMergedHead->next = Merge(pHead1->next, pHead2);
}
else
{
pMergedHead = pHead2;
pMergedHead->next = Merge(pHead1, pHead2->next);
}
return pMergedHead;
}
void ShowList(ListNode* L)
{
ListNode *p =L;
while (p)
{
cout<<p->value<<' ';
p=p->next;
}
cout<<endl;
}结果如下：
个人感觉值得注意的地方有下面几个：
（1）如果链表1，2为空，要考虑代码的鲁棒性。
（2）要考虑链表1，2中某结点的数值相等的情况，这个在else中包含了。
（3）递归调用何时退出？ 递归退出的条件与为了防止空链表造成异常的判断是一个：
if(pHead1 == NULL)
return pHead2;
else if(pHead2 == NULL)
return pHead1;这就是这个代码很巧妙的地方，往往使一行代码两个甚至多个作用，我们举这样的例子： 链表1 ： 1 3 链表2 ： 2 4 首先执行Merge(1,2)函数，进入if， 进入第一次递归，执行Merge(3,2)，显然会进入else， 进入第二次递归，执行Merge(3,4)，显然会进入if， 进入第三次递归，执行Merge(NULL,4)，此时就进入了是否为空的判断，并返回4，同时递归结束。
（4）新的链表何时链接？ 我们可以这样理解这件事，还是上面的例子： 链表1 ： 1 3 链表2 ： 2 4 代码会第一次进入后再递归三次，递归结束后要return四次（从里向外），每一次return时都会将链表向前链接一个结点，每一次return的结果其实是这样： 1. 4 2. 3 4 3. 2 3 4 4.1 2 3 4