### 這道題可以用遞歸很方便的解決,但是可能會暴棧,所以此次用迭代寫。思路就根據代碼慢慢體會吧,這道題最好是畫兩個鏈表,跟著圖走一遍就了解了。
```
SList* merge(SList *pHead1, SList *pHead2)
{
// 兩個 if 為邊界條件,之后的處理都建立在兩個鏈表都不為空的情況下
if (pHead1 == nullptr) {
return nullptr;
}
if (pHead2 == nullptr) {
return nullptr;
}
SList *newHead = nullptr; // 新的鏈表頭
SList *pList1 = pHead1, *pList2 = pHead2;
if (pList1->m_data <= pList2->m_data) {
newHead = pList1;
pList1 = pList1->m_next;
} else {
newHead = pList2;
pList2 = pList2->m_next;
}
SList *pNewListTail = newHead; // 保存新鏈表的尾部
while (pList1 != nullptr && pList2 != nullptr) {
if (pList1->m_data <= pList2->m_data) {
pNewListTail->m_next = pList1;
pNewListTail = pNewListTail->m_next;
pList1 = pList1->m_next;
} else {
pNewListTail->m_next = pList2;
pNewListTail = pNewListTail->m_next;
pList2 = pList2->m_next;
}
}
// 如果某個鏈表還有剩余節點,直接用pNewListTail連過去就好了
if (pList1 != nullptr) {
pNewListTail->m_next = pList1;
}
if (pList2 != nullptr) {
pNewListTail->m_next = pList2;
}
// 返回新鏈頭
return newHead;
}
```