# 21. Merge Two Sorted Lists

https://leetcode.com/problems/merge-two-sorted-lists/

## 題目概要

給定兩個鏈結串列 list1, list2，合併兩個鏈結串列並且由小到大排序。


## 解題技巧

- 解題技巧我用備註寫上了，看備註應該很好懂。

## 程式碼

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} list1
 * @param {ListNode} list2
 * @return {ListNode}
 */
var mergeTwoLists = function (list1, list2) {
  /* cur 用於遍歷, dummy 用於占住頭節點, 
   * 當鏈結串列生成完後, 只需要 return dummy.next 就可以返回整個鏈結串列結果
   */
  let cur = new ListNode();
  let dummy = cur;

  /*
   * 1. 如果兩個鏈結串列中都還有值，那就互相比較哪個值小，將 cur.next 指向該節點，並且將 cur 往後移。
   * 2. 若其中一個鏈結串列的 next 指向空的節點時，代表另外一個鏈結串列剩餘的數已然大於該鏈結串列，所以直接放到當前結果後方即可。
   */

  // 1. 兩個鏈結串列都還有值的情況
  if (list1 !== null && list2 !== null) {
    if (list1.val < list2.val) {
      cur.next = list1; // 等價於 cur.push(list1);
      list1 = list1.next; // 等價於 i++
    } else {
      cur.next = list2;
      list2 = list2.next;
    }
    // 以上操作只將 cur.next 指向節點，但卻沒有讓 cur 往下走，所以需要將 cur 往後一位
    cur = cur.next;
  }

  // 2. 其中一個鏈結串列已經沒有值，直接將鏈結串列剩餘的值放到最後。
  if (list1 !== null) {
    /* 假設當前 list1 = null, list2 = 2 -> 3 -> 4, 我們只需將 cur.next 指向 list2, 
     * 除了下一個值 2 會被放過來之外, 本來的 2 -> 3 -> 4 指向關係也會一起被放進來, 所以只需要做一次就可以
     */
    cur.next = list1;
  } else if (list2 !== null) {
    cur.next = list2;
  }

  /*
   * 為什麼是返回 dummy.next 卻不是返回 dummy?
   * 因為 cur 一開始指向的是一個空節點, 所以 dummy.next 開始才是我們需要的結果
   */
  return dummy.next;
};