21. Merge Two Sorted Lists

Easy

Description

給定兩個已排序的鏈結串列 list1 和 list2，將它們合併成一個排序的鏈結串列並回傳。新串列應由兩個串列的節點拼接而成。

Example:

Input: list1 = [1,2,4], list2 = [1,3,4] Output: [1,1,2,3,4,4]

Intuition#

核心思路：用 dummy head 簡化邊界處理，每次比較兩個串列的當前節點，將較小的接上。

類似 Merge Sort 的合併步驟
Dummy head 避免處理「新串列第一個節點」的特殊情況
當其中一個串列用完，直接接上另一個串列的剩餘部分

Approaches#

1: Recursive#

概念: 比較兩個頭節點，較小者的 next 指向遞迴合併的結果
時間複雜度: O(n + m) - n、m 為兩串列長度
空間複雜度: O(n + m) - 遞迴呼叫堆疊

class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        if (list1 == null) return list2
        if (list2 == null) return list1

        return if (list1.`val` <= list2.`val`) {
            list1.next = mergeTwoLists(list1.next, list2)
            list1
        } else {
            list2.next = mergeTwoLists(list1, list2.next)
            list2
        }
    }
}

⭐2: Iterative with Dummy Head#

概念: 建立 dummy head，用一個 tail 指針追蹤合併串列的尾端，每次將較小的節點接上
時間複雜度: O(n + m) - 每個節點恰好處理一次
空間複雜度: O(1) - 只使用常數額外空間

class Solution {
    fun mergeTwoLists(list1: ListNode?, list2: ListNode?): ListNode? {
        val dummy = ListNode(0)
        var tail = dummy
        var l1 = list1
        var l2 = list2

        while (l1 != null && l2 != null) {
            if (l1.`val` <= l2.`val`) {
                tail.next = l1
                l1 = l1.next
            } else {
                tail.next = l2
                l2 = l2.next
            }
            tail = tail.next!!
        }

        tail.next = l1 ?: l2

        return dummy.next
    }
}

🔑 Takeaways#

Pattern: Dummy head 是鏈結串列題目的萬用技巧，凡是「建構新串列」的題目都優先考慮
關鍵技巧: tail.next = l1 ?: l2 一行搞定剩餘串列的接合，Kotlin 的 Elvis 運算符很方便