題目
輸入兩個遞增排序的鏈表，合并這兩個鏈表并使新鏈表中的節(jié)點仍然是遞增排序的。
例如食拜，輸入圖3.11中的鏈表1和鏈表2脚牍，則合并之后升序鏈表如鏈表3所示。
1.png
思路：先合并兩條鏈表艇棕，在使用兩個指針比較值進行交換結(jié)點位置
3.png
分析
- 1、分析兩個鏈表的合并過程
分析從合并兩個鏈表的頭結(jié)點開始。鏈表1的頭結(jié)點的值小于鏈表2的頭結(jié)點的值矢渊，因此鏈表1的頭結(jié)點是合并后的頭結(jié)點
- 2、剩余結(jié)點的合并
在兩個鏈表中剩下的結(jié)點依然是排序的枉证，因此合并這兩個鏈表的步驟和前面一樣矮男。還是比較兩個頭結(jié)點的值。此時鏈表2的頭結(jié)點小于鏈表1的頭結(jié)點的值室谚，因此鏈表2的頭結(jié)點的值將是合并剩余結(jié)點得到的鏈表的頭結(jié)點毡鉴。再把這個結(jié)點和前面合并鏈表時得到的鏈表的尾結(jié)點鏈接起來。
- 3秒赤、最后
兩個鏈表剩余的結(jié)點依然是排序的猪瞬，因此合并的步驟和之前的步驟是一樣的，這就是典型的遞歸過程入篮，可以使用遞歸函數(shù)完成
算法實現(xiàn)
#include <iostream>
using namespace std;
struct ListNode {
int m_nValue;
ListNode *m_pNext;
};
ListNode* Merge(ListNode *pHead1, ListNode *pHead2)
{
if (pHead1 == nullptr) {
return pHead2;
} else if (pHead2 == nullptr){
return pHead1;
}
ListNode *pMergeHead = nullptr;
if (pHead1->m_nValue < pHead2->m_nValue) {
pMergeHead = pHead1;
pMergeHead->m_pNext = Merge(pHead1->m_pNext, pHead2);
} else {
pMergeHead = pHead2;
pMergeHead->m_pNext = Merge(pHead1, pHead2->m_pNext);
}
return pMergeHead;
}
非遞歸實現(xiàn)
ListNode *Merge2(ListNode *pHead1, ListNode *pHead2) {
// 新建一個頭節(jié)點陈瘦，用來存合并的鏈表
ListNode *head = new ListNode();
head->m_pNext = nullptr;
ListNode *root = head;
while (pHead1 != nullptr && pHead2 != nullptr) {
if (pHead1->m_nValue < pHead2->m_nValue) {
head->m_pNext = pHead1;
head = pHead1;
pHead1 = pHead1->m_pNext;
} else {
head->m_pNext = pHead2;
head = pHead2;
pHead2 = pHead2->m_pNext;
}
}
// 把未結(jié)束的鏈表連接到合并后的鏈表尾部
if (pHead1 != nullptr) {
head->m_pNext = pHead1;
} else if (pHead2 != nullptr) {
head->m_pNext = pHead2;
}
return root->m_pNext;
}
參考
《劍指offer》
