觀前提醒：

1. 我預設大家已經先思考並分析過題目，沒啥想法才開始 google 找解題靈感。若無，建議每題先花 1~2 顆番茄鐘的時間來分析題目比較好。可參考番茄鐘工作法。
2. 承上，既然已經有思考過了，那我這邊直接 po 題目 + 解題想法 + code +心得 。若已經在 code 內有足夠的註解了，那我可能解題想法 & 心得的部分就不會寫太多，免得干擾你的思考。
3. 所有解法都是已經取得系統的 Accepted，但或許不是最優解法，請多包涵。
4. 最後，歡迎在下面留言指教~教學相長才會進步歐~

題目

Merge two sorted linked lists and return it as a new sorted list. The new list should be made by splicing together the nodes of the first two lists.

Example:

Input: 1->2->4, 1->3->4
Output: 1->1->2->3->4->4

介紹資料結構--Linked List

要解這題，就需要先對維基百科裡面常見的資料結構，鼎鼎大名的 Linked List，來好好地了解一番~

若大家英文版看得霧煞煞，也可以參考這篇由 Chiu CC 大大所寫的 Linked List 中文版教學文，以下節錄部分文章：

Linked list(連結串列)是一種常見的資料結構，其使用node(節點)來記錄、表示、儲存資料(data)，並利用每個node中的pointer指向下一個node，藉此將多個node串連起來，形成Linked list，並以NULL來代表Linked list的終點，見圖一(a)。

若實際打開每個node的內部，至少會包含(1)data來代表資料，與(2)pointer指向下一個node，見圖一(b)：

解題想法

好的，那在看完簡單的教學後，我們知道 Linked List 中任一個 node 一定包含以下重要兩大資訊：

• data -- 代表資料
• pointer -- 指向下一個 node

那接下來，我們需要搞定的問題就是，要把兩串 Sorted Linked List ，按各數字大小，重新組合成一串全新的Linked List。我們可以採取以下策略：

1. 創立一個全新的 ListNode ，來當作主鏈表。(let headNode = new ListNode(0);)
2. 讀取 l1 目前的值與 l2目前的值比較。
   2-1. 如果 l1.val 小於 l2.val，將當前的 l1 節點加入主鏈表，然後把 l1 指向下一個 l1 節點。
   2-2. 如果 l1.val 大於 l2.val，則把 l2 當前的節點加入主鏈表，然後把 l2 指向下一個 l2 節點。
3. 直到 l1 或 l2 一方為 null 則停止比較，並且將另外一邊剩下的節點加入主鏈表。
4. 最後，記得要 return headNode.next，因為一開始(第一步)我們多弄了一個 value 為 0 的頭，不能把它傳回去給 leetcode，會報錯。

那我們就馬上實作看看囉~

CODE

/**
 * 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) {
  // 創立一個全新的 ListNode ，來當作主鏈表。
  let headNode = new ListNode(0);
  let currentNode = headNode;
  // 讀取 l1 目前的值與 l2目前的值比較。
  // 如果 l1.val 小於 l2.val，將當前的 l1 節點加入主鏈表，然後把 l1 指向下一個 l1 節點。
  // 如果 l1.val 大於 l2.val，則把 l2 當前的節點加入主鏈表，然後把 l2 指向下一個 l2 節點。
  while (l1 !== null && l2 !== null) {
    if (l1.val < l2.val) {
      currentNode.next = l1;
      l1 = l1.next;
    } else {
      currentNode.next = l2;
      l2 = l2.next;
    }
    currentNode = currentNode.next;
  }
  // 直到 l1 或 l2 一方為 null 則停止比較，並且將另外一邊剩下的節點加入result。
  if (l1 === null) {
    currentNode.next = l2;
  } else if (l2 === null) {
    currentNode.next = l1;
  }
  return headNode.next;
};

心得

• 如果大家跟小弟一樣，對於資料結構都是新手的話，我個人蠻推薦以下這本書(博客來連結，非業配)
  演算法圖鑑：26種演算法 + 7種資料結構，人工智慧、數據分析、邏輯思考的原理和應用全圖解
  它可以幫助你快速了解常用的演算法 + 資料結構，不用艱澀的專有名詞，步步口語分解，真心推薦。
• 推薦一個免費資源，那就是 VISUALGO.NET。他是一個專門介紹資料結構的互動教學網頁，可以進去嘗試玩玩看，這樣會對資料結構更有FU歐~

謝謝大家的收看，LeetCode 小學堂我們下次見~