Welcome to Michael's Blog! 🎉 currently Renew and moving old post 🫠

Easy 21 - Merge Two Sorted Lists

In this blog I will share a solution to the Merge Two Sorted Lists problem.

Loading comments...

題目連結

難度：Easy

You are given the heads of two sorted linked lists list1 and list2.Merge the two lists in a 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.Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]
Example 2:
Input: list1 = [], list2 = []
Output: []
Example 3:
Input: list1 = [], list2 = [0]
Output: [0]
Linked List
Two Pointers
Recursion

解題思路

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

  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. 邊界條件的處理
    • 特別注意處理了空串列的情況
    • 當其中一個串列為空時，直接返回另一個串列

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

Loading comments...
Easy 02 - Valid Parentheses
In this blog I will share a solution to the Valid Parentheses problem.
Medium 53 - Maximum Subarray
In this blog I will share a solution to the maximum subarray problem.