一、題目描述

將兩個升序鏈表合并為一個新的升序鏈表并返回，新鏈表是通過拼接給定的兩個鏈表的所有節點組成的，比如：

• 輸入：1->2->4, 1->3->4
• 輸出：1->1->2->3->4->4

二、解題思路

2.1 迭代法

使用循環迭代的方法，依次找出較小的節點鏈接起來即可：

• 比較 l1 和 l2 當前節點值的大小
• 將較小的節點鏈接到 l3 尾部
• l1 或 l2 指針后移一位
• l3 指針后移一位
• 循環結束：l1 和 l2 其中一個遍歷到尾部
• 將未遍歷完的節點全部鏈接到 l3 尾部
• 返回保存的 l3 頭指針 head->next

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 1. 升序鏈表 l3
        ListNode *l3 = new ListNode(0);

        // 2. 保存頭指針用于返回結果
        ListNode *head = l3;

        while (l1 && l2) {
            // 3. 選擇較小的節點連接到 l3 尾部
            if (l1->val <= l2->val) {
                l3->next = l1;
                l1 = l1->next;
            } else {
                l3->next = l2;
                l2 = l2->next;
            }

            l3 = l3->next;
        }

        // 將多余的 l1 或者 l2 節點直接鏈接到 l3 尾部
        l3->next = (l1 == nullptr ? l2 : l1);

        return head->next;
    }
};

復雜度分析

• 時間復雜度：O(m + n)，循環的次數等于 2 個鏈表的總長度 m + n
• 空間復雜度：O(1)，使用的變量內存為常數級別

2.2 遞歸法

遞歸法要注意遞歸表達式和循環結束條件：

• 當 l1 為空，返回 l2
• 當 l2 為空，返回 l1
• l1 和 l2 都不為空，比較節點 val
• 將較小的節點鏈接上，并遞歸調用函數來確定下一個鏈接的節點

遞歸法不是很好理解，建議用 vs 調試看下內存。

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 1. 遞歸結束條件
        if (l1 == nullptr)
            return l2;

        // 2. 遞歸結束條件
        if (l2 == nullptr)
            return l1;

        // 3. 遞歸表達式
        if (l1->val <= l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

復雜度分析

• 時間復雜度：O(m + n)，每次遞歸都會添加一個鏈表節點，最終會遞歸 m + n 次
• 空間復雜度：遞歸的過程中，會將全部 m + n 個節點都保存一次在遞歸調用棧中