21. 合併兩個有序鏈表

思路

因為兩個鏈表有序的，因此每次只需要比較鏈表最前面的數字，
然後取比較小的連到當前更新的節點上。

當其中一個鏈表走到結尾時，無須再比較，將合併到一半的鏈表接上還沒用完的鏈表。

如果不想先比較最開始的數字，就先在前面創建一個空的節點，指向答案的起點。

程式碼

1. 鏈表

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        if(list1 == nullptr || list2 == nullptr) return list1 == nullptr ? list2 : list1;
        ListNode* head = list1 -> val < list2 -> val ? list1 : list2;
        ListNode* cur1 = head -> next;
        ListNode* cur2 = head == list1 ? list2 : list1;
        ListNode* prev = head;
        while(cur1 != nullptr && cur2 != nullptr) {
            if(cur1 -> val <= cur2 -> val) {
                prev -> next = cur1;
                cur1 = cur1 -> next;
            }
            else {
                prev -> next = cur2;
                cur2 = cur2 -> next;
            }
            prev = prev -> next;
        }
        prev -> next = cur1 != nullptr ? cur1 : cur2;
        return head;
    }
};

2. 鏈表, 使用哨兵節點

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode();
        ListNode* tail = head;
        while(list1 != nullptr && list2 != nullptr) {
            if(list1->val < list2->val) {
                tail->next = list1;
                list1 = list1->next; 
            }
            else {
                tail->next = list2;
                list2 = list2->next;
            }
            tail = tail->next;
        }
        tail->next = list1 != nullptr ? list1 : list2;
        return head->next;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(1)$