?這篇文章我們繼續來講鏈表中很經典的面試題：合并有序鏈表。
目錄
迭代
遞歸
?我們首先來看一下這張圖片里面的要求，給你兩個鏈表，要求把他們按照從小到大的方式排列。
這里涉及到幾個問題，首先，我們的頭節點是不是要釋放一個？而且我們把該節點連接到另外一個鏈表的某個節點上的時候？會不會存在指針丟失的問題？就算你鏈接的很穩妥，那么這里又會涉及到時間復雜度和空間復雜度的問題。
好了，不多說了，再說就要被自己繞暈了哈哈，初學者就是不需要想很多，遇到鏈表的題，無非三種路徑，雙指針，迭代，遞歸。
我們先來看好理解的迭代的方法。當然這道題的雙指針和迭代其實也是殊途同歸。本質上是一樣的。
迭代
我們可以用迭代的方法來實現上述算法。當 l1 和 l2 都不是空鏈表時，判斷 l1 和 l2 哪一個鏈表的頭節點的值更小，將較小值的節點添加到結果里，當一個節點被添加到結果里之后，將對應鏈表中的節點向后移一位。
所以這其實是一種暴力求法，也就是說，我一個個拿出來比較，因為我的原鏈表是有序的，所以不存在重復比較的過程。所以我就大膽給兩個鏈表各一個變量去遍歷然后比較。
當然，這里為什么要自定義一個哨兵位頭節點？因為有了頭節點能夠更好更容易返回我們合并后的鏈表。這里把代碼給大家放一下，稍微填了一些注釋。
class Solution {
public:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {auto dummy = new ListNode(0);auto cur = dummy;while( list1 && list2 ){auto pp = (list1->val < list2->val) ? &list1 : &list2; // 獲取倆鏈表當前值小的結點cur->next = *pp; // cur 指向值小的結點cur = cur->next; // cur 后移*pp = (*pp)->next; // *pp 也要后移，不然下次循環比較的還是舊的list1或list2結點}// 循環結束，list1 和 list2 其中有一個為空，但不知道是哪個cur->next = (list1) ? list1 : list2;return dummy->next;}
};遞歸
我們再來看遞歸。遞歸其實難的不是想不想的到，難的是對自我返回條件的判定。簡單的說，難的是這個遞歸該做到哪一步。怎么回歸。當然，如果你做的多了，很快很自然就能想到我為什么需要去限制比較的條件呢，或者說我回歸的應該是節點，我的條件的判斷才應該是比較。
所以代碼如下：
public class Solution {public ListNode MergeTwoLists(ListNode l1, ListNode l2) {if (l1 == null) {return l2;} else if (l2 == null) {return l1;} else if (l1.val < l2.val) {l1.next = MergeTwoLists(l1.next, l2);return l1;} else {l2.next = MergeTwoLists(l1, l2.next);return l2;}}
}好了，這道題就講到這里
如果你覺得對你有幫助，可以點贊關注加收藏，感謝您的閱讀，我們下一篇文章再見。
一步步來，總會學會的，首先要懂思路，才能有東西寫。
》)
