LeetCode 0021. Merge Two Sorted Lists 題解

LeetCode 0021. Merge Two Sorted Lists 是一道基本的鏈結串列（Linked List）題目，基本的操作包含指針的使用，以及如果需要創建新的鏈結串列時，可以使用一個偽頭節點（dummy node）佔位的技巧。

在本站的碼不停題系列文章中，筆者會採「一題一解」的方式，並且只提供 Java 程式語言版本的程式範例，其他程式語言的範例程式以及不同解法，則會放置於這個站點上。

題意理解

給定兩個已排序的鏈結串列 list1 和 list2，要求合併這兩個鏈結串列，並返回合併後有序鏈結串列的頭節點。

解法：迭代遍歷

思路想法

題目給定的鏈結串列 list1 和 list2 是有序遞增的，可以分別使用指針 p1 和 p2 分別遍歷兩個鏈結串列，並根據 p1.val 和 p2.val 的大小關係確定添加順序，交替地前進直至遍歷完畢。

具體實作中有一些注意事項：

引入偽頭節點：當需要創建一條新的鏈結串列時，經常會引入一個 dummy 節點用來簡化邊界情況的處理，由於僅作為邊界處理不涉及實際操作，因此被稱作「啞節點」或「虛擬頭節點」。
注意檢查剩餘：循環條件中的判斷式，是只要當 p1 或 p2 為 null 時便停止，需要將剩餘部分再合併入結果中。

範例程式

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        ListNode p1 = list1;
        ListNode p2 = list2;

        while (p1 != null && p2 != null) {
            if (p1.val > p2.val) {
                curr.next = p2;
                p2 = p2.next;
            } else {
                curr.next = p1;
                p1 = p1.next;
            }

            curr = curr.next;
        }

        curr.next = p1 != null ? p1 : p2;

        return dummy.next;
    }
}

實作時將指針 p1 和 p2 宣告出來，在腦海中想像時會比較有感覺；如果更為熟悉一點的話，由於 list1 和 list2 本身傳入時就用於標示鏈結串列的位置，並且此題遍歷完成之後便毋須回頭使用 list1 和 list2，因此也可以再簡化如下：

class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode dummy = new ListNode(-1);
        ListNode curr = dummy;

        while (list1 != null && list2 != null) {
            if (list1.val > list2.val) {
                curr.next = list2;
                list2 = list2.next;
            } else {
                curr.next = list1;
                list1 = list1.next;
            }

            curr = curr.next;
        }

        curr.next = list1 != null ? list1 : list2;

        return dummy.next;
    }
}

複雜度分析

時間複雜度：\( \mathcal{O} (m + n) \)，其中 \( m \) 和 \( n \) 分別為鏈結串列 list1 和 list2 的長度。
空間複雜度：\( \mathcal{O} (1) \)。