【LeetCode】#21. Merge Two Sorted Lists 詳細完整解法

Merge Two Sorted Lists

題目要求

給你兩個整理好順序的Linked List,將這兩個Linked List合併成一個Linked List。

回傳合併後的Linked List的head來檢查。

其他限制條件

  • Linked List的節點數量範圍都是在[0, 50]之間。
  • 節點的數值為 -100 ≤ Node.val ≤ 100。
  • 兩組Linked List都已經按照升序的排列方式整理好了。

解題思路

邊緣案例

限制條件中,節點數量的範圍在[0, 50],所以需要考慮到可能出現0個節點的狀況。我們可以在程式碼的最前面加上邊緣判斷來處理。

if(!list1) return list2;   
if(!list2) return list1;   

當list1的節點數量是0就回傳list2,反過來list2數量是0時就回傳list1,而當兩個都是節點數量都是0的時候,回傳list1或者list2都不會影響答案,第一行的邏輯就可以處理兩個節點數量都是0的狀況。

1. 直覺解/疊代(Iterative)方法

這一題的要求並不難,只需要兩邊比大小,將所有節點按照小到大的順序排列起來就可以了。

這裡我們先規劃幾個大步驟:

  1. 防止邊緣案例。
  2. 決定第一個節點。
  3. 建立現在位置的指針,用來指向下一個節點。
  4. 用疊代法對list1和list2的現在節點進行比大小,決定現在位置指針的下一個節點。
  5. 將剩下的節點連接起來。

程式碼

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        //防止邊緣案例
        if(!list1) return list2;
        if(!list2) return list1;
        
        //決定第一個節點
        ListNode* newList;
        if(list1->val < list2->val){
            newList = list1;
            list1 = list1->next;
        }else{
            newList = list2;
            list2 = list2->next;
        }
        
        //建立節點指針
        ListNode* cur = newList;

        //比大小,並將指針指向下一個節點,直到list1和list2其中一個走到尾巴為止。
        while(list1 && list2){
            if(list1->val < list2->val){
                cur->next = list1;
                list1 = list1->next;
            }else{
                cur->next = list2;
                list2 = list2->next;
            }             
            cur = cur->next;
        }

        //將指針指向剩下的節點,完成所有連接
        if(!list1) cur->next = list2;
        else cur->next = list1;
        
        return newList;
    }
};

時間複雜度分析

程式碼只用了一個迴圈,當最短的list走到底後跳出,取兩個list中最短的長度做為執行時間的依據,不論是list1或者list2的長度都是未知的n,所以時間複雜度為O(n)。

空間複雜度分析

除了引數外,另外宣告了兩個節點指針用來回傳結果及完成疊代,疊代過程中沒有使用到任何新的空間,空間複雜度上為O(1)。

2. 遞迴(遞歸)方法—Recursive

在這個題目中,只需要做到三件事,比較、合併、回傳結果,從0個節點到最大數量的Linked List都可以使用相同的模式處理,符合遞迴的條件。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        
        //防止邊緣案例
        if(!list1) return list2;
        if(!list2) return list1;
        
        //取數值較小的作為head,並將head的下一個節點指向下一輪的節點的合併結果。
        if(list1->val < list2->val)
            list1->next = mergeTwoLists(list1->next,list2);
        else
            list2->next = mergeTwoLists(list1,list2->next);
              
				//回傳list1和list2之中數值較小的節點,也就是head。
        return list1->val < list2->val ? list1 : list2;
    }
};

時間複雜度分析

遞迴法會一直執行到碰觸到邊緣案例,才會停止繼續呼叫自己,也就是發生其中一個節點走完的狀況,不論是list1,list2的節點長度都是n,所以時間複雜度為O(n)。

空間複雜度分析

遞迴法完全在兩個節點之中處理,不需要額外宣告變數,時間複雜度為O(1)。

在〈【LeetCode】#21. Merge Two Sorted Lists 詳細完整解法〉中有 1 則留言

  1. 自動引用通知: 【LeetCode】 刷題地圖 - 人生自習室

發佈留言

發佈留言必須填寫的電子郵件地址不會公開。 必填欄位標示為 *

回到頂端