LeetCode如何合并兩個(gè)有序鏈表

一、題目描述

將兩個(gè)升序鏈表合并為一個(gè)新的升序鏈表并返回，新鏈表是通過(guò)拼接給定的兩個(gè)鏈表的所有節(jié)點(diǎn)組成的，比如：

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

二、解題思路

2.1 迭代法

使用循環(huán)迭代的方法，依次找出較小的節(jié)點(diǎn)鏈接起來(lái)即可：

• 比較 l1 和 l2 當(dāng)前節(jié)點(diǎn)值的大小
• 將較小的節(jié)點(diǎn)鏈接到 l3 尾部
• l1 或 l2 指針后移一位
• l3 指針后移一位
• 循環(huán)結(jié)束：l1 和 l2 其中一個(gè)遍歷到尾部
• 將未遍歷完的節(jié)點(diǎn)全部鏈接到 l3 尾部
• 返回保存的 l3 頭指針 head->next

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

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

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

            l3 = l3->next;
        }

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

        return head->next;
    }
};

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(m + n)，循環(huán)的次數(shù)等于 2 個(gè)鏈表的總長(zhǎng)度 m + n
• 空間復(fù)雜度：O(1)，使用的變量?jī)?nèi)存為常數(shù)級(jí)別

2.2 遞歸法

遞歸法要注意遞歸表達(dá)式和循環(huán)結(jié)束條件：

• 當(dāng) l1 為空，返回 l2
• 當(dāng) l2 為空，返回 l1
• l1 和 l2 都不為空，比較節(jié)點(diǎn) val
• 將較小的節(jié)點(diǎn)鏈接上，并遞歸調(diào)用函數(shù)來(lái)確定下一個(gè)鏈接的節(jié)點(diǎn)

遞歸法不是很好理解，建議用 vs 調(diào)試看下內(nèi)存。

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

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

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

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(m + n)，每次遞歸都會(huì)添加一個(gè)鏈表節(jié)點(diǎn)，最終會(huì)遞歸 m + n 次
• 空間復(fù)雜度：遞歸的過(guò)程中，會(huì)將全部 m + n 個(gè)節(jié)點(diǎn)都保存一次在遞歸調(diào)用棧中