【Leetcode 筆記】21. Merge Two Sorted Lists

題目解釋

給定兩個已排序的 linked list list1 和 list2 的 head。 將兩個 linked list 合併為一個排序過的 linked list。

這個 linked list 應該透過將前兩個 linked list 的 node 拼接在一起來形成。傳回 merged linked list 的 head。

範例

• 輸入: list1 = [1, 2, 4], list2 = [1, 3, 4]
• 輸出: [1, 1, 2, 3, 4, 4]

輸出就是合併後的 linked list。

最佳解法

步驟

1. 先令一個空 Node head 作為 linked list 的起點
2. 初始化 curr 指標指向 head
3. 開始 traverse list1 跟 list2
   • 數值小的優先成為 curr.next
   • 總之要記得將 curr 前進一格 (curr = curr.next)
4. 如果 traverse 完 list1 或 list2 還有剩的話就直接將後面的部分加入 curr 後面 (因為有 sorted 過)

NOTE: 要 return head.next，因為 head 本身是一個 dummy node。

程式碼

class Solution:
    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
        head = ListNode(None, None)
        curr = head

        while list1 and list2:
            if list1.val <= list2.val:
                curr.next = list1
                list1 = list1.next
            else:
                curr.next = list2
                list2 = list2.next
            curr = curr.next

        if list1:
            curr.next = list1
        if list2:
            curr.next = list2

        return head.next

時間複雜度

O(n + m)，其中 n 是 list1 的長度，m 是 list2 的長度。

空間複雜度

O(1)。

結語

基本上三個 test case 都有過就會全過的一題，也是高頻題。

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26