iT邦幫忙

第 12 屆 iThome 鐵人賽

DAY 29
1
自我挑戰組

[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ系列 第 29

[LeetCode with JavaScript] Day 29: Merge Two Sorted Lists

觀前提醒:

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

題目

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)。
Imgur
若實際打開每個node的內部,至少會包含(1)data來代表資料,與(2)pointer指向下一個node,見圖一(b):
Imgur

解題想法

好的,那在看完簡單的教學後,我們知道 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;
};

心得


謝謝大家的收看,LeetCode 小學堂我們下次見~/images/emoticon/emoticon29.gif


上一篇
[LeetCode with JavaScript] Day 28: First Unique Character in a String
下一篇
[LeetCode with JavaScript] Day 30: Reverse Linked List
系列文
[LeetCode with JavaScript] 一起來刷 LeetCode吧 ~~~ (ノ>ω<)ノ30
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

尚未有邦友留言

立即登入留言