題目分析 

• 給兩個已排序的 linked lists list1 、list2 。
• 將兩個 linked list 合併，並且一樣要排序好。

第一直覺

var mergeTwoLists = function (list1, list2) {
  let dummy = new ListNode(); // 宣告 dummy 方便最後回傳
  let tail = dummy; // 將 tail 指向 dummy，用來串接新鏈表
  while (list1 && list2) {
    if (list1.val < list2.val) {
      tail.next = list1; // 較小的節點接到 tail 後面
      list1 = list1.next; // 移至下一個節點
    } else {
      tail.next = list2;
      list2 = list2.next;
    }
    tail = tail.next; // 將 tail 指向最後一個節點
  }
  tail.next = list1 || list2; // 將剩餘節點連接到尾端
  return dummy.next; // 回傳 dummy.next 也就是 tail 的頭節點
};

優化寫法

• 使用遞規的方式處理

var mergeTwoLists = function(list1, list2) {
    if (!list1) return list2;  // 如果 list1 為空，直接返回 list2
    if (!list2) return list1;  // 如果 list2 為空，直接返回 list1
    
    // 選擇較小的節點作為新鏈表的頭節點
    if (list1.val < list2.val) {
        list1.next = mergeTwoLists(list1.next, list2);  // 遞歸合併剩餘的節點
        return list1;
    } else {
        list2.next = mergeTwoLists(list1, list2.next);  // 遞歸合併剩餘的節點
        return list2;
    }
};