LeetCode-21.合并兩個有序連結清單

21.題目：

将兩個升序連結清單合并為一個新的 升序 連結清單并傳回。新連結清單是通過拼接給定的兩個連結清單的所有節點組成的。 
輸入：l1 = [1,2,4], l2 = [1,3,4]
輸出：[1,1,2,3,4,4]
示例 2：

輸入：l1 = [], l2 = []
輸出：[]
示例 3：

輸入：l1 = [], l2 = [0]
輸出：[0]

來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/merge-two-sorted-lists
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
           

代碼：

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode();
    let curr = dummy;
    while(l1 !== null && l2 !== null) {
        if(l1.val < l2.val) {
            curr.next = l1;
            l1 = l1.next;
        } else {
            curr.next = l2;
            l2 = l2.next;
        }
        curr = curr.next;
    }
    if (l1 !== null) {
        curr.next = l1;
    } else {
        curr.next = l2;
    }
    return dummy.next;
};

           

圖解算法：

題解：

1. 首先，合并兩個有序連結清單，從題目中我們可以知道兩個資訊，一個是有序，一個是連結清單。
2. 建立一個虛拟節點，目前指針指向虛拟節點；
3. 當

   l1連結清單

   和

   l2連結清單

   均不為空的情況下，就要進行一一對比；
4. 當

   l1.val < l2.val

   ， 就說明

   l1

   的值比

   l2

   的值要小，是以目前指針的

   next

   指向

   l1

   ，

   l1

   向後走一位；
5. 反之，則是

   curr.next = l2.val, l2 = l2.next

   ;
6. 如果循環比較到其中一個連結清單已經為空的情況下，就可以将還沒比較完的l1或者l2直接連結在後面；
7. 最後，傳回虛拟節點的下一位。