DAY 18 試題

問題描述

給定兩個已經排序的鏈結串列 list1 和 list2，請將這兩個鏈結串列合併為一個新的已排序的鏈結串列，並且結合兩個鏈結串列的節點，不需要創建新的節點。要求返回合併後的鏈結串列的頭節點。

例如：

• 輸入：list1 = [1,2,4]，list2 = [1,3,4] 輸出：[1,1,2,3,4,4]
• 輸入：list1 = []，list2 = [] 輸出：[]
• 輸入：list1 = []，list2 = [0] 輸出：[0]

解題思路

此問題可以使用雙指針的方式來合併兩個已排序的鏈結串列。具體步驟如下：

1. 初始化一個虛擬頭節點：我們可以先建立一個虛擬節點 dummy 作為結果鏈結串列的起點，這樣可以簡化處理過程中的邊界情況。
2. 遍歷兩個鏈結串列：使用兩個指針分別指向 list1 和 list2 的當前節點，根據當前節點的值比較來決定將哪個節點接入合併鏈結串列中。較小值的節點會被移動到結果鏈結串列的末端，並且對應的指針移動到下一個節點。
3. 處理剩餘節點：當其中一個鏈結串列遍歷完成時，直接將另一個鏈結串列的剩餘部分接在結果鏈結串列的後面。
4. 返回結果：最後返回虛擬節點的下一個節點，這就是合併後的鏈結串列的頭節點。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        // 創建一個虛擬頭節點
        ListNode dummy;
        ListNode* tail = &dummy;
        
        // 遍歷兩個鏈結串列
        while (list1 && list2) {
            if (list1->val < list2->val) {
                tail->next = list1;
                list1 = list1->next;
            } else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        
        // 處理剩餘的節點
        if (list1) {
            tail->next = list1;
        } else {
            tail->next = list2;
        }
        
        return dummy.next;
    }
};

解法重點與分析

1. 雙指針技術：本題使用雙指針遍歷 list1 和 list2，每次選擇較小的節點接入合併鏈結串列中，並移動對應的指針到下一個節點。
2. 虛擬頭節點的作用：使用虛擬頭節點可以簡化操作，避免處理合併過程中的邊界情況，例如當一個鏈結串列為空時。
3. 處理剩餘部分：當其中一個鏈結串列遍歷完畢後，直接將另一個鏈結串列的剩餘部分接在結果鏈結串列的末端。
4. 時間複雜度：合併的過程需要遍歷兩個鏈結串列，總的時間複雜度為 O(n + m)，其中 n 和 m 分別是兩個鏈結串列的長度。
5. 空間複雜度：由於不需要額外的資料結構來儲存節點，除了返回結果之外，使用的額外空間是常數級別，因此空間複雜度為 O(1)。

總結

此題旨在合併兩個已排序的鏈結串列，通過雙指針技術，我們能夠高效地將兩個鏈結串列合併成一個新的排序鏈結串列，並且在過程中保持原有的節點結構，無需創建新節點。這種解法的時間複雜度為 O(n + m)，空間複雜度為 O(1)，非常適合處理鏈結串列合併的問題。

以上是第十八天的自學內容分享，謝謝大家。