[[414979]]

本文轉載自微信公眾號「三分鐘學前端」，作者sisterAn。轉載本文請聯系三分鐘學前端公眾號。

將兩個升序鏈表合并為一個新的升序鏈表并返回。新鏈表是通過拼接給定的兩個鏈表的所有節點組成的。

示例：

輸入：1->2->4, 1->3->4 
輸出：1->1->2->3->4->4 

解答：

確定解題的數據結構： 單鏈表

確定解題思路： 從鏈表頭開始比較，l1 與 l2 是有序遞增的，所以比較 l1.val 與 l2.val 的較小值就是合并后鏈表的最小值，次小值就是小節點的 next.val 與大節點的 val 比較的較小值，依次遞歸，直到遞歸到 l1 l2 均為 null

畫圖實現： 畫圖幫助理解一下

確定邊界條件： 當遞歸到任意鏈表為 null ，直接將 next 指向另外的鏈表即可，不需要繼續遞歸了

代碼實現：

function mergeTwoLists(l1, l2) { 
    if(l1 === null) { 
        return l2 
    } 
    if(l2 === null) { 
        return l1 
    } 
    if(l1.val <= l2.val) { 
        l1.next = mergeTwoLists(l1.next, l2) 
        return l1 
    } else { 
        l2.next = mergeTwoLists(l2.next, l1) 
        return l2 
    } 
} 

來源：https://github.com/sisterAn/JavaScript-Algorithms