Easy 21 - Merge Two Sorted Lists

解題思路

這題是要合併兩個已排序的鏈結串列，主要的思路是：

1. 處理邊界情況：當其中一個串列為空時，直接返回另一個串列
2. 比較兩個串列當前節點的值，選擇較小的節點
3. 遞迴處理剩餘的節點
4. 返回合併後的串列

複雜度分析

• 時間複雜度：O(n + m)，其中 n 和 m 分別是兩個串列的長度
• 空間複雜度：O(n)，遞迴調用會使用堆疊空間

解題狀態機 (XState 風格)

stateDiagram-v2
    [*] --> CHECK_EMPTY

    state CHECK_EMPTY {
        [*] --> 檢查空值
        檢查空值 --> 返回非空串列: 其中一個為空
        檢查空值 --> 比較節點: 都不為空
    }

    state 比較節點 {
        [*] --> 選擇較小節點
        選擇較小節點 --> 遞迴處理
    }

    比較節點 --> CHECK_EMPTY: 遞迴
    返回非空串列 --> [*]

解題步驟

1. 檢查是否有空串列，如果有則返回非空的串列
2. 比較兩個串列當前節點的值
3. 選擇較小的節點，並遞迴處理剩餘節點
4. 返回合併後的結果

實作

function mergeTwoLists(list1, list2) {
  // 使用 ?? 運算子處理空值情況
  if (!list1 || !list2)
    return list1 ?? list2;

  const [smaller, bigger] = list1.val ≤ list2.val ? [list1, list2] : [list2, list1];
  smaller.next = mergeTwoLists(smaller.next, bigger);
  return smaller;
}

解題心得

在解這道合併排序鏈結串列的題目時，我有幾個重要的發現和優化：

1. 解構賦值的運用

   • 使用 const [smaller, bigger] = ... 的解構賦值
   • 讓程式碼更具可讀性
   • 避免了多餘的暫存變數

2. 邊界條件的處理

   • 特別注意處理了空串列的情況
   • 當其中一個串列為空時，直接返回另一個串列

透過遞迴的方式，我們可以用最少的程式碼完成這個看似複雜的任務，搭配解構賦值和空值合併運算子，讓程式碼更簡潔。