21. Merge Two Sorted Lists

題目網址：https://leetcode.cn/problems/merge-two-sorted-lists/

題意：給兩個 sorted linked list: list1 和 list2, 將兩個合併成一個 sorted linked list。

Solution：

想法：利用 dummy node, 其中 tail 指向當前 val 較小的 list node

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode *dummy = new 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; // 指向下一個
        }

        // 某中一個 list 結束跳出迴圈, 要處理另一個 list 剩下的元素
        if (list1) {
            tail->next = list1;
        } else if (list2) {
            tail->next = list2;
        }

        return dummy->next;
    }
};

• time：$O(m + n)$ ➔ 其中 m 為 list1 的長度, n 為 list2 的長度, worse case：每個點都恰拜訪一次
• space：$O(1)$ ➔ 只需常數空間