runtime 4 ms, beats 94.91% of cpp submissions
O(n) solution with explanation

tags: linked list, pointer

📖 description

給定兩個 sorted list ， merge 成一個 sorted list 。

ex.
    list1 = 1->2->4
    list2 = 1->3->4

    merge = 1->1->2->3->4->4

🧠 solution

merge sort 的 merge 部分，將數值比較小的點放在當前 list 的尾巴，然後繼續往後走，直到兩個 list 都走完為止，時做起來很簡單，所以這題比較像是在思考如何最佳化整體的架構

有兩個重要的點可以考慮

  • dummy node，簡化程式碼
  • reuse node，解省空間跟時間

dummy node

透過在 list 的頭部放一個假的初始點，可以直接在後方更新節點，減少多餘的程式碼，回傳時只要給 dummy node 的 next 就可以了

reuse node

本題包括了兩個地方，在更新後方節點時不是直接用 new 的，而是使用原本那兩個 list 的節點，而當更新到其中一個結束時，我們可以直接接上另一個 list 當前的位置，來加速以及減少使用空間。

⏳ time complexity

總時間複雜度 **

📝 code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head = new ListNode();            // dummy node
        auto tmp = head;
        ListNode* node;
        while(list1!=nullptr && list2!=nullptr){
            if(list1->val<list2->val){
                node = list1;
                list1 = list1->next;
            }
            else{
                node = list2;
                list2 = list2->next;
            }
            tmp->next = node;                       // reuse node
            tmp = tmp->next;
        }
        if(list1!=nullptr) tmp->next = list1;       // reuse node
        if(list2!=nullptr) tmp->next = list2;
        return head->next;
    }
};