C++算法之 合并兩個有序鏈表
來源：程序員人生 發布時間：2014-12-23 08:09:28 閱讀次數：2812次
題目：合并兩個已排序好的鏈表
方法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個鏈表就能夠了，也就是前面合并好的鏈表自動鏈接上另外沒有遍歷完的鏈表的那部份！
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
