前言

嘿嘿～今天要解的題目是：Merge Two Sorted Lists（合併兩個排序鏈結串列）。
這題目就是給我們兩個已經排好序的鏈結串列，要求我們把它們合併成一個新的排序好的鏈結串列！
聽起來是不是很像把兩堆資料整理成一堆呢？
別擔心，我們一步步來，肯定能輕鬆搞定～

英文題目 Merge Two Sorted Lists

難度：Easy

題目描述：

You are given the heads of two sorted linked lists list1 and list2. Merge the two lists into one sorted list.
The list should be made by splicing together the nodes of the first two lists. Return the head of the merged linked list.

給定兩個已經排好序的鏈結串列 list1 和 list2，將它們合併成一個新的排序好的鏈結串列。
這個新鏈結串列應該由兩個鏈結串列中的節點拼接在一起構成。

範例 1：

輸入： list1 = [1, 2, 4]，list2 = [1, 3, 4]

輸出： [1, 1, 2, 3, 4, 4]

範例 2：

輸入： list1 = []，list2 = []

輸出： []

範例 3：

輸入： list1 = []，list2 = [0]

輸出： [0]

中文描述

給定兩個排序的單向鏈結串列，將它們合併成一個新的排序好的鏈結串列，並返回這個新鏈結串列的頭節點。

思考過程

1. 理解問題需求：

   題目要求我們將兩個已經排序的鏈結串列合併成一個排序好的鏈結串列。
   意思是需要保持順序地將兩個鏈結串列的節點拼接在一起。
   最好的方式是一次從兩個鏈結串列中取出最小的節點，然後依次將它們連接到新鏈結串列中。

2. 創建虛擬頭節點（dummy node）：

   • 為什麼需要一個虛擬頭節點？
     • 如果我們直接在鏈結串列上進行操作，會涉及處理很多特殊情況，比如：新鏈結串列的第一個節點是來自 list1 還是 list2？用一個虛擬節點來簡化這些操作，使我們只需要專注於如何拼接節點，而不需要處理頭節點的特殊情況。
   • 虛擬頭節點其實就是一個臨時的節點，我們的最終目標是返回虛擬節點後面的那一串合併好的鏈結串列。

3. 使用雙指針遍歷兩個鏈結串列：

   • 為什麼用雙指針？

     • list1 和 list2 都是已經排序好的鏈結串列，所以我們只需要比較當前的兩個節點（list1 和 list2），將較小的節點連接到新鏈結串列中，然後將對應的指針移動到下一個節點。
     • 我們的目標是：保持兩個指針始終指向它們各自鏈結串列中的當前最小節點，然後將較小的節點插入到新鏈結串列的最後。

   • 具體步驟：

     1. 初始化一個指針 current，它指向虛擬節點，我們會通過 current 來逐步連接合併後的新節點。
     2. 進入 while 循環，當 list1 和 list2 都還有未處理的節點時，進行比較：
        • 如果 list1.val 比 list2.val 小，說明 list1 當前的節點應該被放入新鏈結串列。我們就讓 current.next 指向 list1 的當前節點，然後將 list1 的指針移動到下一個節點。
        • 如果 list2.val 更小或相等，那麼 list2 的當前節點應該被放入新鏈結串列，類似地，我們讓 current.next 指向 list2，然後將 list2 的指針移動到下一個節點。
     3. 無論 list1 還是 list2，每次選取較小的節點後，都要把 current 指針移動到剛連接的節點，準備好下一次比較。

4. 處理剩餘節點：

   • 當其中一個鏈結串列遍歷完了之後，另一個鏈結串列可能還有未處理的節點。
   • 因為這些剩餘的節點已經是排序好的，我們可以直接將剩下的鏈結串列連接到新鏈結串列的尾部。
   • 在 while 循環結束後，我們只需要檢查 list1 和 list2 哪一個不為空，把它直接接在 current.next 上即可。

5. 返回新鏈結串列：

   • 最後一步，我們要返回合併後的新鏈結串列。由於我們一開始創建了一個虛擬頭節點，我們的結果實際上從 dummy.next 開始。因此，我們返回 dummy.next 即可。

實作程式碼註解

class ListNode {
    val: number;
    next: ListNode | null;
    constructor(val?: number, next?: ListNode | null) {
        this.val = val === undefined ? 0 : val;
        this.next = next === undefined ? null : next;
    }
}

function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {
    // 創建一個虛擬頭節點，方便處理
    const dummy = new ListNode(0);
    let current = dummy; // 用來追蹤新鏈結串列的最後一個節點

    // 當 list1 和 list2 都不為空時，進行比較
    while (list1 !== null && list2 !== null) {
        if (list1.val < list2.val) {
            // 如果 list1 的值小於 list2，那就把 list1 當前節點加到新鏈結串列中
            current.next = list1;
            list1 = list1.next; // 移動 list1 指針到下一個節點
        } else {
            // 否則，list2 的值較小或相等，將 list2 當前節點加到新鏈結串列中
            current.next = list2;
            list2 = list2.next; // 移動 list2 指針到下一個節點
        }
        // 移動 current 指針到新鏈結串列的最後一個節點
        current = current.next;
    }

    // 當其中一個鏈結串列遍歷完了之後，直接將剩餘的節點接在新鏈結串列的尾部
    current.next = list1 !== null ? list1 : list2;

    // 返回新鏈結串列的頭節點，即 dummy.next
    return dummy.next;
}

思路：

• 步驟 1：首先，初始化一個虛擬節點 dummy 和一個指針 current，用來追蹤新鏈結串列的最後位置。虛擬節點的好處是可以簡化處理，不需要專門關心新鏈結串列的頭部問題。

• 步驟 2：進入 while 循環，當 list1 和 list2 都還有節點時，不斷比較這兩個節點的值，將較小的節點接在新鏈結串列的尾部，並將 current 指針移動到新加的節點。

• 步驟 3：當有一個鏈結串列遍歷完了之後，直接將剩下的鏈結串列接在新鏈結串列尾部，因為剩下的部分已經是排序好的。

• 步驟 4：最後返回 dummy.next，這樣就可以得到合併後的新鏈結串列。

這樣的處理方式能夠確保我們在 O(n) 的時間內完成合併操作，並保持鏈結串列的排序。

本次要點：

• 使用虛擬頭節點來簡化鏈結串列的拼接操作。
• 使用雙指針遍歷兩個鏈結串列，按大小順序拼接節點。
• 確保合併後的新鏈結串列仍然保持排序。

學會這個技巧之後，處理鏈結串列的問題就像組裝樂高一樣簡單好玩！
每次拼接一個節點，看到最終的合併結果是不是很有成就感呢？
下次我們再來一起挑戰更多有趣的題目吧！💪 (~￣▽￣)~