力扣23-合并K个升序链表

字数统计: 1.4k字 | 阅读时长: 6分

2020-09-26

摘要: 合并 K 个升序链表，堆与分治

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

今天我们继续看一道经典题(陈题)，leetcode第23题，合并 K 个升序链表。

本题有两个主流解法：

算法1：堆
算法2：分治

这两个都是在 leetcode 上能整理出几十道题的常见算法，并且有一定难度，周赛的 B 和 C 题中经常会出现。

本题还有一个简化版本，就是链表二路归并 21. 合并两个有序链表，这是链表归并排序的合并过程。类似地还有数组二路归并 88. 合并两个有序数组，这是数组的归并排序的合并过程。

很多链表的操作会以本题为组件，例如 leetcode 第 355 题，设计推特，等等。

下面我们看一下这个题。

$1 题目

23. 合并K个升序链表

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

提示：

k == lists.length
0 <= k <= 10^4
0 <= lists[i].length <= 500
-10^4 <= lists[i][j] <= 10^4
lists[i] 按 升序 排列
lists[i].length 的总和不超过 10^4

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
1->4->5,
1->3->4,
2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：
输入：lists = []
输出：[]

示例 3：
输入：lists = [[]]
输出：[]

$2 题解

算法1：堆

维护容量为 k 的最小堆，里面始终维护当前的最多 k 个链表的最小元素的排序，堆顶为这 k 个链表最小元素中的最小的，归并后链表的下一个元素即为堆顶元素，将堆头出堆，并将堆头对应的链表节点的下一节点进堆，如果没有下一节点则跳过。

将所有元素均访问一遍后，按照出堆顺序组织的新链表就是归并后的链表。

堆的容量为 $K$，因此插入删除时间复杂度 $O(\log K)$，最多有 $KN$ 个节点，因此时间复杂度 $O(NK\log K)$。

代码 (C++)

自定义比较的方法1：定义结构体，里面只重载 ()

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        priority_queue<ListNode*, vector<ListNode*>, Cmp> pq;
        for(ListNode *iter : lists)
        {
            if(iter != nullptr)
                pq.push(iter);
        }
        if(pq.empty()) return  nullptr;
        ListNode *top = pq.top();
        pq.pop();
        ListNode *result = top;
        if(top -> next != nullptr)
            pq.push(top -> next);
        ListNode *tail = result;
        while(!pq.empty())
        {
            ListNode *top = pq.top();
            pq.pop();
            tail -> next = top;
            if(top -> next != nullptr)
                pq.push(top -> next);
            tail = tail -> next;
        }
        return result;
    }

private:
    struct Cmp
    {
        bool operator () (ListNode *left, ListNode *right)
        {
            return (left -> val) > (right -> val); // > 是小顶堆；< 是大顶堆
        }
    };
};

自定义比较的方法法二

bool operator <(const ListNode &left, const ListNode &right)
{
    // 形参必须写引用
    return (left.val) > (right.val);
}

class Solution_2 {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        priority_queue<ListNode> pq;
        for(ListNode *iter : lists)
        {
            if(iter != nullptr)
                pq.push(*iter);
        }
        if(pq.empty()) return  nullptr;
        ListNode top = pq.top();
        pq.pop();
        if(top.next != nullptr)
            pq.push(*(top.next));
        ListNode *result = new ListNode(top.val);
        ListNode *tail = result; // 迭代的时候还是用指针
        while(!pq.empty())
        {
            ListNode top = pq.top();
            pq.pop();
            if(top.next != nullptr)
                pq.push(*(top.next));
            tail -> next = new ListNode(top.val);
            tail = tail -> next;
        }
        return result;
    }
};

算法2：分治

目标是归并 K 个链表，用分治的思维模式：

分解：将 K 个链表分为两份，每份 K / 2 个链表
解决：如果 K = 1，可以直接解决，将链表直接返回即可
合并：将两个有序链表归并成一个

考虑递归的合并过程，第一轮合并 $\frac{K}{2}$ 组链表，每一组的时间为 $O(2N)$；第二轮合并 $\frac{K}{4}$ 组链表，每一组的时间为 $O(4N)$，以此类推。

因此总时间复杂度 $O(\sum\limits_{i=1}\limits^{\log K}\frac{K}{2^{i}} \times 2^{i}N) = O(KN\log K)$。

代码：自顶向下 (C++)

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        int n = lists.size();
        ListNode *result = _mergeKLists(lists, 0, n - 1);
        return result;
    }

private:
    ListNode* _mergeKLists(vector<ListNode*>& lists, int left, int right)
    {
        if(left == right)
            return lists[left];
        if(left + 1 == right)
            return _mergeTwoLists(lists[left], lists[right]);
        int mid = left + (right - left) / 2;
        ListNode *left_merged = _mergeKLists(lists, left, mid - 1);
        ListNode *right_merged = _mergeKLists(lists, mid, right);
        return _mergeTwoLists(left_merged, right_merged);
    }

    ListNode* _mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *result = new ListNode(-1);
        ListNode *cur = result;
        while (l1 && l2) {
            if(l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            } else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return result -> next;
    }
};

代码：自底向上 (C++)

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.empty()) return nullptr;
        int n = lists.size();
        while (n > 1)
        {
            // n 每轮减小一半
            int k = (n + 1) / 2;
            for(int i = 0; i < n / 2; ++i)
                lists[i] = _mergeTwoLists(lists[i], lists[i + k]);
            n = k;
        }
        return lists[0];
    }

private:
    ListNode* _mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *result = new ListNode(-1);
        ListNode *cur = result;
        while (l1 && l2) {
            if(l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            } else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        if(l1) cur->next = l1;
        if(l2) cur->next = l2;
        return result -> next;
    }
};

潮汐朝夕的生活实验室 \Doge 陪伴一个算法工程师的职业生涯

算法leetcode