LeetCode第21題_Merge Two Sorted Lists (Easy)

LeetCode第21題_Merge Two Sorted Lists (Easy)

- 6月 23, 2021

https://leetcode.com/problems/merge-two-sorted-lists/

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]

Constraints:

The number of nodes in both lists is in the range [0, 50].
-100 <= Node.val <= 100
Both list1 and list2 are sorted in non-decreasing order.

題目給我們兩個已經排列過的LinkedList

那需要我們把此兩個LinkedList給合在並回傳也排序後的List

[1,3,5,7]

[2,4,6,8]

->[1,2,3,4,5,6,7,8]

常見錯誤做法：

1.不能單純只透過改pointer來改順序，合併兩個有序列表需要進行元素的比較和選擇，僅僅改變指針的順序無法實現這一目的。

2.直接使用兩個循環進行比較：這種方法通常會忽略兩個列表已經有序的特點，導致不必要的比較操作和額外的時間複雜度。

通常會想成說把node 1指標改從原本指向到3改先安插指到2

node 2的指標再從指向4改接續指向3

實際上會出現一個問題就是當我們把node 1原先指向node 3的pointer改成指到2時候

就無任何人指向node 3了。(再也取不到node 3了也無法繼續排序下去)

不能只透過改pointer來做順序調整

你需要有兩個手法

一開始會有兩個list pointer分別list1,list2

分別指向最小的起始node 後續每次跌代比對會順移至下一個最小的

再來還需要一個dummy head 這個node(當中的值不重要)

我們會需要以它來作為開頭，建立排序後的list。

當兩個連結串列分別是 1 -> 3 -> 5 -> 7 和 2 -> 4 -> 6 -> 8 時

list1: 1 -> 3 -> 5 -> 7

list2: 2 -> 4 -> 6 -> 8

創建一個假節點(dummy node)作為新連結串列的起始節點

dummy -> NULL

初始化遍歷指針 curr 指向假節點(dummy node)：

dummy -> NULL

curr

開始進行迴圈遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上。

同時，將對應的遍歷指針向後移動：

list1: 3 -> 5 -> 7

list2: 2 -> 4 -> 6 -> 8

dummy -> 1 -> NULL

curr

繼續遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上

list1: 3 -> 5 -> 7

list2: 4 -> 6 -> 8

dummy -> 1 -> 2 -> NULL

curr

繼續遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上

list1: 5 -> 7

list2: 4 -> 6 -> 8

dummy -> 1 -> 2 -> 3 -> NULL

curr

繼續遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上

list1: 5 -> 7

list2: 6 -> 8

dummy -> 1 -> 2 -> 3 -> 4 -> NULL

curr

繼續遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上

list1: 7

list2: 6 -> 8

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> NULL

curr

繼續遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上

list1: 7

list2: 8

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> NULL

curr

繼續遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上

list1: NULL

list2: 8

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> NULL

curr

繼續遍歷，比較兩個連結串列的節點值，並將較小的節點連接到新連結串列上

list1: NULL

list2: NULL

dummy -> 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8 -> NULL

curr

最終得到了合併後的連結串列 1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7 -> 8

因此最不理想情況下就是

兩個List各自長度分別M跟N，時間複雜度就是 O(M+N)

但不一定都會試M+N次，因為其中有一個List比較短就直接中斷即可直接原封不動把

剩餘較長的list補上。(題目有說兩個list都是排序過的)

初階等級作法:

優點：使用迴圈和條件判斷來遍歷兩個有序列表並合併它們。

缺點：這個作法需要使用額外的記憶體空間來建立合併後的新列表，並需要遍歷和排序整個列表，時間複雜度較高。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* dummy = new ListNode(0);
        ListNode* curr = dummy;

        while (list1 && list2) {
            if (list1->val <= list2->val) {
                curr->next = list1;
                list1 = list1->next;
            } else {
                curr->next = list2;
                list2 = list2->next;
            }
            curr = curr->next;
        }

        curr->next = list1 ? list1 : list2;
        ListNode* result = dummy->next;
        delete dummy;

        return result;
    }
};

ListNode* dummy = new ListNode(0);

創建一個新的 ListNode 物件，並將其指標分配給 dummy。這個節點被稱為假節點(dummy node)，值為0。
假節點是用於簡化合併列表的過程，它的下一個指向最終合併後的列表。

ListNode* curr = dummy;
創建一個指標 curr，並將其初始化為dummy。這個指標curr用於遍歷合併後的列表，最初指向假節點(dummy node)。

while (list1 && list2) {....}
進入一個 while 迴圈，只要 list1 和 list2 都還有節點，就繼續執行迴圈內的程式。


if (list1->val <= list2->val) {
    curr->next = list1;
    list1 = list1->next;
} else {
    curr->next = list2;
    list2 = list2->next;
}
判斷 list1 和 list2 目前節點的值，如果 list1 的值小於等於 list2 的值，則將 curr 的下一個指向 list1，並將 list1 的指標往後移動到下一個節點。如果 list1 的值大於 list2 的值，則將 curr 的下一個指向 list2，並將 list2 的指標往後移動到下一個節點。


curr = curr->next;
將 curr 的指標往後移動到下一個節點，準備處理下一個節點的合併。


curr->next = list1 ? list1 : list2;
退出 while 迴圈後，將剩餘的 list1 或 list2 接到 curr 的下一個節點，這是因為其中一個列表可能還有未處理的節點。

ListNode* result = dummy->next;
將合併後的列表的起始節點指標設為 result，即假節點(dummy node)的下一個節點。

delete dummy;
釋放假節點(dummy node)的記憶體，避免內存洩漏。
return result;
回傳合併後的列表的起始節點指標，即 result。

進階作法：

優點：這個作法遞迴地合併兩個有序列表，使用分治演算法的概念。不需要額外的記憶體空間，只需在原地修改列表的指標。

缺點：這個作法可能在處理非常長的列表時遇到深度遞迴限制，可能導致堆疊溢出的問題。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if (!list1) return list2;
        if (!list2) return list1;

        if (list1->val <= list2->val) {
            list1->next = mergeTwoLists(list1->next, list2);
            return list1;
        } else {
            list2->next = mergeTwoLists(list1, list2->next);
            return list2;
        }
    }
};

if (!list1) return list2;

if (!list2) return list1;

檢查 list1 和 list2 是否為空。如果其中一個列表為空，則直接返回另一個列表，因為空列表不需要進行合併操作。

if (list1->val <= list2->val) {

list1->next = mergeTwoLists(list1->next, list2);

return list1;

} else {

list2->next = mergeTwoLists(list1, list2->next);

return list2;

}

在這段程式中，比較 list1 和 list2 目前節點的值。

如果 list1 的值小於等於 list2 的值，則將 list1 的下一個節點指向遞迴調用 mergeTwoLists 函式的結果，並返回 list1 作為合併後的列表的起始節點。

否則，將 list2 的下一個節點指向遞迴調用 mergeTwoLists 函式的結果，並返回 list2 作為合併後的列表的起始節點。

這種作法使用了遞迴，通過比較兩個列表的值並將節點串聯起來，達到合併列表的目的。

遞迴的終止條件是其中一個列表為空，此時直接返回非空列表即可。

遞迴的過程中，不斷比較兩個列表的值並遞歸調用 mergeTwoLists 函式，直到其中一個列表遍歷完畢。

留言