题目：合并两个已排序好的链表
方法1:
两个链表
比如链表1： 1->3->5->7->9
链表2： 2->4->6->8->10
跟我们合并两个数组1样，链表1的头结点 和链表2的头节点比较，如果链表1头节点的值大于链表2头接点的值，
那末链表2的头结点为合并链表的头结点，那末链表1的头节点继续和链表2的第2个节点（剩余链表2的头结点）
作比较，但1个链表遍历完以后，如果另外1个链表还没有遍历完，由于链表本来就是排序的，所以让合并链表的
尾巴节点指向未遍历完链表的头结点就能够
举个例子：
链表1： 1，3，5，23，34；
链表2： 2，4，6，8，10；
当遍历以后 链表3：1，2，3，4，8，10 此时链表2已遍历完，while循环退出，但是剩余链表1还有 23，34
此时 让链表3的尾巴节点10 链接 剩余链表的头节点 23 就能够了
<span style="color:#000000;">// 合并链表.cpp : 定义控制台利用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
struct ListNode
{
int m_Data;
ListNode* m_pNext;
ListNode(int value,ListNode* next = NULL):m_Data(value),m_pNext(next){}
};
/*
两个链表 比如链表1： 1->3->5->7->9
链表2： 2->4->6->8->10
跟我们合并两个数组1样，链表1的头结点 和链表2的头节点比较，如果链表1头节点的值大于链表2头接点的值，
那末链表2的头结点为合并链表的头结点，那末链表1的头节点继续和链表2的第2个节点（剩余链表2的头结点）
作比较，但1个链表遍历完以后，如果另外1个链表还没有遍历完，由于链表本来就是排序的，所以让合并链表的
尾巴节点指向未遍历完链表的头结点就能够
举个例子：
链表1： 1，3，5，23，34；
链表2： 2，4，6，8，10；
当遍历以后 链表3：1，2，3，4，8，10 此时链表2已遍历完，while循环退出，但是剩余链表1还有 23，34
此时 让链表3的尾巴节点10 链接 剩余链表的头节点 23 就能够了
*/
ListNode* MergeList2(ListNode* head1,ListNode* head2)
{
if (head1 == NULL)
{
return head2;
}
else if(head2 == NULL)
{
return head1;
}
ListNode* MergeHead = NULL;
if (head1->m_Data < head2->m_Data)
{
MergeHead = head1;
head1 = head1->m_pNext;
}
else
{
MergeHead = head2;
head2 = head2->m_pNext;
}
ListNode* tmpNode = MergeHead;
while (head1&&head2)
{
if (head1->m_Data < head2->m_Data)
{
MergeHead->m_pNext = head1;
head1 = head1->m_pNext;
}
else
{
MergeHead->m_pNext = head2;
head2 = head2->m_pNext;
}
MergeHead = MergeHead->m_pNext;
}
if (head1)
{
MergeHead->m_pNext = head1;
}
if (head2)
{
MergeHead->m_pNext = head2;
}
return tmpNode;
}
int _tmain(int argc, _TCHAR* argv[])
{
ListNode* pHead1 = new ListNode(1);
ListNode* pCur = pHead1;
for (int i = 3; i < 10; i+=2)
{
ListNode* tmpNode = new ListNode(i);
pCur->m_pNext = tmpNode;
pCur = tmpNode;
}
ListNode* pHead2 = new ListNode(2);
pCur = pHead2;
for (int j = 4; j < 10; j+=2)
{
ListNode* tmpNode = new ListNode(j);
pCur->m_pNext = tmpNode;
pCur = tmpNode;
}
ListNode* head = MergeList2(pHead1,pHead2);
while (head)
{
cout<<head->m_Data<<" ";
head=head->m_pNext;
}
getchar();
return 0;
}</span>
方法2：
/*
我们分析两个链表的进程，首先从合并两个链表的头结点开始，链表1的头节点的值小于链表2的头结点的值，因此链表1的头结点
就是合并链表的头节点，继续合并剩下的链表，在两个链表中剩余的节点依然是排序的，因此合并两个链表的步骤是1样的，我们还是比较两个头结点的
值，此时链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是合并剩余链表的头结点，我们把这个节点和前面合并链表时得到的链表的尾巴节点
链接起来
依照上面的分析可知：每次合并的步骤都是1样的，由此我们想到了递归。
*/
// 合并链表.cpp : 定义控制台利用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
struct ListNode
{
int m_Data;
ListNode* m_pNext;
ListNode(int value,ListNode* next = NULL):m_Data(value),m_pNext(next){}
};
/*
我们分析两个链表的进程，首先从合并两个链表的头结点开始，链表1的头节点的值小于链表2的头结点的值，因此链表1的头结点
就是合并链表的头节点，继续合并剩下的链表，在两个链表中剩余的节点依然是排序的，因此合并两个链表的步骤是1样的，我们还是比较两个头结点的
值，此时链表2的头结点的值小于链表1的头结点的值，因此链表2的头结点是合并剩余链表的头结点，我们把这个节点和前面合并链表时得到的链表的尾巴节点
链接起来
依照上面的分析可知：每次合并的步骤都是1样的，由此我们想到了递归。
*/
ListNode* MergeList(ListNode* pHead1,ListNode* pHead2)
{
if (pHead1 == NULL)
{
return pHead2;
}
else if (pHead2 == NULL)
{
return pHead1;
}
ListNode* pMergeHead = NULL;
if (pHead1->m_Data < pHead2->m_Data)
{
pMergeHead = pHead1;
pMergeHead->m_pNext = MergeList(pHead1->m_pNext,pHead2);
}
else
{
pMergeHead = pHead2;
pMergeHead->m_pNext = MergeList(pHead1,pHead2->m_pNext);
}
return pMergeHead;
}
int _tmain(int argc, _TCHAR* argv[])
{
ListNode* pHead1 = new ListNode(1);
ListNode* pCur = pHead1;
for (int i = 3; i < 10; i+=2)
{
ListNode* tmpNode = new ListNode(i);
pCur->m_pNext = tmpNode;
pCur = tmpNode;
}
ListNode* pHead2 = new ListNode(2);
pCur = pHead2;
for (int j = 4; j < 10; j+=2)
{
ListNode* tmpNode = new ListNode(j);
pCur->m_pNext = tmpNode;
pCur = tmpNode;
}
ListNode* head = MergeList2(pHead1,pHead2);
while (head)
{
cout<<head->m_Data<<" ";
head=head->m_pNext;
}
getchar();
return 0;
}
看了这道题目，那末上次的合并数组也能够用递归这里附上代码：
<span style="color:#000000;">// MergeArray.cpp : 定义控制台利用程序的入口点。
//
#include "stdafx.h"
#include <iostream>
using namespace std;
//递归方法
void MergeArray2(int a[],int aCount,int b[],int blen)
{
int len = aCount+blen⑴;
aCount--;
blen--;
if (aCount < 0)
{
while (blen>=0)
{
a[len--] = b[blen--];
}
return;
}
if (a[aCount] > b[blen])
{
a[len] = a[aCount];
MergeArray2(a,aCount,b,++blen);
}
else
{
a[len] = b[blen];
MergeArray2(a,++aCount,b,blen);
}
}
void MergeArray(int a[], int aCount, int b[], int blen)//aCount为a数组实际（狭义）长度，blen为b数组实际长度
{
int len = aCount + blen - 1;//合并数组的长度也就是a数组的广义长度
aCount--;
blen--;
while (aCount>=0 && blen>=0)
{
if (a[aCount] >= b[blen])
{
a[len--] = a[aCount--];
}
else
{
a[len--] = b[blen--];
}
}
while(blen >= 0)
{
a[len--] = b[blen--];
}
}
int _tmain(int argc, _TCHAR* argv[])
{
int a[] = {2,4,6,8,10,0,0,0,0,0};
int b[] = {1,3,5,7,9};
MergeArray2(a,5,b,5);
for (int i = 0; i < sizeof(a)/sizeof(a[0]); i++)
{
cout<<a[i]<<" ";
}
getchar();
return 0;
}</span>
个人感觉合并数组用递归不太好，由于斟酌如果1个数组遍历完另外一个数组还没有遍历完这个情况有点麻烦，而如果是链表的话，1个数链表历完，
那末这个链表为空，则返回另外1个链表就能够了，也就是前面合并好的链表自动链接上另外没有遍历完的链表的那部份！