C++算法之 合并兩個(gè)有序鏈表
來源：程序員人生 發(fā)布時(shí)間：2014-12-23 08:09:28 閱讀次數(shù)：2817次
題目：合并兩個(gè)已排序好的鏈表
方法1:
兩個(gè)鏈表
比如鏈表1： 1->3->5->7->9
鏈表2： 2->4->6->8->10
跟我們合并兩個(gè)數(shù)組1樣，鏈表1的頭結(jié)點(diǎn) 和鏈表2的頭節(jié)點(diǎn)比較，如果鏈表1頭節(jié)點(diǎn)的值大于鏈表2頭接點(diǎn)的值，
那末鏈表2的頭結(jié)點(diǎn)為合并鏈表的頭結(jié)點(diǎn)，那末鏈表1的頭節(jié)點(diǎn)繼續(xù)和鏈表2的第2個(gè)節(jié)點(diǎn)（剩余鏈表2的頭結(jié)點(diǎn)）
作比較，但1個(gè)鏈表遍歷完以后，如果另外1個(gè)鏈表還沒有遍歷完，由于鏈表本來就是排序的，所以讓合并鏈表的
尾巴節(jié)點(diǎn)指向未遍歷完鏈表的頭結(jié)點(diǎn)就能夠
舉個(gè)例子：
鏈表1： 1，3，5，23，34；
鏈表2： 2，4，6，8，10；
當(dāng)遍歷以后 鏈表3：1，2，3，4，8，10 此時(shí)鏈表2已遍歷完，while循環(huán)退出，但是剩余鏈表1還有 23，34
此時(shí) 讓鏈表3的尾巴節(jié)點(diǎn)10 鏈接 剩余鏈表的頭節(jié)點(diǎn) 23 就能夠了
<span style="color:#000000;">// 合并鏈表.cpp : 定義控制臺(tái)利用程序的入口點(diǎn)。
//
#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){}
};
/*
兩個(gè)鏈表 比如鏈表1： 1->3->5->7->9
鏈表2： 2->4->6->8->10
跟我們合并兩個(gè)數(shù)組1樣，鏈表1的頭結(jié)點(diǎn) 和鏈表2的頭節(jié)點(diǎn)比較，如果鏈表1頭節(jié)點(diǎn)的值大于鏈表2頭接點(diǎn)的值，
那末鏈表2的頭結(jié)點(diǎn)為合并鏈表的頭結(jié)點(diǎn)，那末鏈表1的頭節(jié)點(diǎn)繼續(xù)和鏈表2的第2個(gè)節(jié)點(diǎn)（剩余鏈表2的頭結(jié)點(diǎn)）
作比較，但1個(gè)鏈表遍歷完以后，如果另外1個(gè)鏈表還沒有遍歷完，由于鏈表本來就是排序的，所以讓合并鏈表的
尾巴節(jié)點(diǎn)指向未遍歷完鏈表的頭結(jié)點(diǎn)就能夠
舉個(gè)例子：
鏈表1： 1，3，5，23，34；
鏈表2： 2，4，6，8，10；
當(dāng)遍歷以后 鏈表3：1，2，3，4，8，10 此時(shí)鏈表2已遍歷完，while循環(huán)退出，但是剩余鏈表1還有 23，34
此時(shí) 讓鏈表3的尾巴節(jié)點(diǎn)10 鏈接 剩余鏈表的頭節(jié)點(diǎn) 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：
/*
我們分析兩個(gè)鏈表的進(jìn)程，首先從合并兩個(gè)鏈表的頭結(jié)點(diǎn)開始，鏈表1的頭節(jié)點(diǎn)的值小于鏈表2的頭結(jié)點(diǎn)的值，因此鏈表1的頭結(jié)點(diǎn)
就是合并鏈表的頭節(jié)點(diǎn)，繼續(xù)合并剩下的鏈表，在兩個(gè)鏈表中剩余的節(jié)點(diǎn)依然是排序的，因此合并兩個(gè)鏈表的步驟是1樣的，我們還是比較兩個(gè)頭結(jié)點(diǎn)的
值，此時(shí)鏈表2的頭結(jié)點(diǎn)的值小于鏈表1的頭結(jié)點(diǎn)的值，因此鏈表2的頭結(jié)點(diǎn)是合并剩余鏈表的頭結(jié)點(diǎn)，我們把這個(gè)節(jié)點(diǎn)和前面合并鏈表時(shí)得到的鏈表的尾巴節(jié)點(diǎn)
鏈接起來
依照上面的分析可知：每次合并的步驟都是1樣的，由此我們想到了遞歸。
*/
// 合并鏈表.cpp : 定義控制臺(tái)利用程序的入口點(diǎn)。
//
#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){}
};
/*
我們分析兩個(gè)鏈表的進(jìn)程，首先從合并兩個(gè)鏈表的頭結(jié)點(diǎn)開始，鏈表1的頭節(jié)點(diǎn)的值小于鏈表2的頭結(jié)點(diǎn)的值，因此鏈表1的頭結(jié)點(diǎn)
就是合并鏈表的頭節(jié)點(diǎn)，繼續(xù)合并剩下的鏈表，在兩個(gè)鏈表中剩余的節(jié)點(diǎn)依然是排序的，因此合并兩個(gè)鏈表的步驟是1樣的，我們還是比較兩個(gè)頭結(jié)點(diǎn)的
值，此時(shí)鏈表2的頭結(jié)點(diǎn)的值小于鏈表1的頭結(jié)點(diǎn)的值，因此鏈表2的頭結(jié)點(diǎn)是合并剩余鏈表的頭結(jié)點(diǎn)，我們把這個(gè)節(jié)點(diǎn)和前面合并鏈表時(shí)得到的鏈表的尾巴節(jié)點(diǎn)
鏈接起來
依照上面的分析可知：每次合并的步驟都是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;
}
看了這道題目，那末上次的合并數(shù)組也能夠用遞歸這里附上代碼：
<span style="color:#000000;">// MergeArray.cpp : 定義控制臺(tái)利用程序的入口點(diǎn)。
//
#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數(shù)組實(shí)際（狹義）長度，blen為b數(shù)組實(shí)際長度
{
int len = aCount + blen - 1;//合并數(shù)組的長度也就是a數(shù)組的廣義長度
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>
個(gè)人感覺合并數(shù)組用遞歸不太好，由于斟酌如果1個(gè)數(shù)組遍歷完另外一個(gè)數(shù)組還沒有遍歷完這個(gè)情況有點(diǎn)麻煩，而如果是鏈表的話，1個(gè)數(shù)鏈表歷完，
那末這個(gè)鏈表為空，則返回另外1個(gè)鏈表就能夠了，也就是前面合并好的鏈表自動(dòng)鏈接上另外沒有遍歷完的鏈表的那部份！
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對(duì)您的學(xué)習(xí)有所幫助,可以手機(jī)掃描二維碼進(jìn)行捐贈(zèng)
