題目鏈接：合并兩個排序的鏈表
解題思路1：迭代
創(chuàng)建一個新的單鏈表，對兩個鏈表進行迭代，每次取較小元素放入新鏈表中，直至某一個鏈表為空，則結(jié)束循環(huán)，接著判斷是否有某個鏈表沒有遍歷結(jié)束，再將未遍歷結(jié)束的鏈表部分放入結(jié)果鏈表中。
一般創(chuàng)建單鏈表，都會設(shè)一個虛擬頭結(jié)點，也叫哨兵，因為這樣每一個節(jié)點都有一個前驅(qū)節(jié)點，完美解決了各種判空邏輯的煩惱，所有的節(jié)點將被統(tǒng)一處理。
代碼如下：文章來源地址http://www.zghlxwxcb.cn/news/detail-619088.html
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
ListNode* vhead = new ListNode(-1);
ListNode* cur = vhead;
while(pHead1!=nullptr && pHead2!=nullptr){
if(pHead1->val <= pHead2->val){
cur->next = pHead1;
pHead1 = pHead1->next;
}else{
cur->next = pHead2;
pHead2 = pHead2->next;
}
cur = cur->next;
}
cur->next = pHead1 ? pHead1 : pHead2;
return vhead->next;
}
解題思路2：遞歸
本題進行迭代求解十分方便，此處還是提供遞歸的解法，增強遞歸的理解。
首先，結(jié)束遞歸的條件：某一個鏈表為空，則返回非空鏈表，遞歸結(jié)束
其次：當前遞歸條件，若pHead1->val < =pHead2->val，將較小的pHead1->next與后面merge的頭連接，即pHead1->next = Merge(pHead1->next, pHead2)，較大時同理
遞歸的返回值：排好序的鏈表頭文章來源：http://www.zghlxwxcb.cn/news/detail-619088.html
代碼如下：
ListNode* Merge(ListNode* pHead1, ListNode* pHead2) {
if(pHead1 == nullptr) return pHead2;
if(pHead2 == nullptr) return pHead1;
if(pHead1->val <= pHead2->val){
pHead1->next = Merge(pHead1->next, pHead2);
return pHead1;
}else{
pHead2->next = Merge(pHead1, pHead2->next);
return pHead2;
}
到了這里，關(guān)于【題解】合并兩個排序的鏈表的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（9）[復(fù)制帶隨機指針的鏈表]](https://imgs.yssmx.com/Uploads/2024/02/672298-1.png)
