[[414979]]

本文轉(zhuǎn)載自微信公眾號(hào)「三分鐘學(xué)前端」，作者sisterAn。轉(zhuǎn)載本文請(qǐng)聯(lián)系三分鐘學(xué)前端公眾號(hào)。

將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回。新鏈表是通過拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的。

示例：

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

解答：

確定解題的數(shù)據(jù)結(jié)構(gòu)： 單鏈表

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

畫圖實(shí)現(xiàn)： 畫圖幫助理解一下

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

代碼實(shí)現(xiàn)：

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