LeetCode 23. 合并 K 个升序链表

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

LeetCode 23. 合并 K 个升序链表原题链接困难

作者：

wzc1995 , 2018-03-28 22:20:31 , 所有人可见 , 阅读 4156

24

4

题目描述

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

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

样例

输入：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

输入：lists = []
输出：[]

输入：lists = [[]]
输出：[]

限制

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。

算法

(二分治合并) $O(nlogk)$

将所有待合并的有序单向链表进行递归分治处理，即将当前链表的序列分成两部分，每部分递归进行合并，然后将当前左右两部分合并的结果再进行二合并即可。

时间复杂度

递归每层的时间复杂度是整个结点个数 $O(n)$，由于每次是二分，所有总共有 $O(logk)$ 层。
故总时间复杂度为 $O(nlogk)$。

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
        ListNode *head = new ListNode(0);
        ListNode *cur = head;
        while (l1 != NULL && l2 != NULL) {
            if (l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            }
            else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        cur -> next = (l1 != NULL ? l1 : l2);
        return head -> next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if (lists.size() == 0)
            return NULL;
        if (lists.size() == 1)
            return lists[0];

        int mid = lists.size() / 2;
        vector<ListNode*> left = vector<ListNode*>(lists.begin(), lists.begin() + mid);
        vector<ListNode*> right = vector<ListNode*>(lists.begin() + mid, lists.end());
        ListNode *l1 = mergeKLists(left);
        ListNode *l2 = mergeKLists(right);
        return merge2Lists(l1, l2);
    }
};

17 评论

IShowMeat 11个月前

递归！把函数当做黑箱！！！！！

koreshiabraham 2021-12-22 00:40

I found that solution very popular and helpful:
https://www.youtube.com/watch?v=L-8LVBPmIpc&ab_channel=EricProgramming

玩笑其 2021-08-17 11:12

请问一下merge2Lists函数中ListNode *head = new ListNode(0);是被new出来的，那什么时候会被delete掉呢？

有心人 2021-08-17 21:17

可以不把 head 设为 ListNode * 指针类型, 而是把 head 设为 ListNode 类型，这样就不用考虑内存的问题了。不把 head作为指针 new出来确实会 节省内存，内存消耗 由 22.1MB 变为 12.7MB。详细说明见题解。

// 分治合并：时间 O(kn * logk), 递归栈空间 O(logk)
class Solution {
public:
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        // dummy是指针,下面要return dummy->next. new指针要开辟内存. 内存消耗 22.1MB
        // auto dummy = new ListNode(-1), cur = dummy;

        // dummy是ListNode 型, 不是ListNode * 型, 要return dummy.next. 内存消耗 12.7MB
        ListNode dummy, *cur = &dummy; 

        while (a && b) // 可以把 while的 "{}" 去掉, if-else 算是一对语句
            if (a->val < b->val) cur = cur->next = a, a = a->next;
            else cur = cur->next = b, b = b->next;

        cur->next = a ? a : b;

        // return dummy->next; // dummy 是指针类型, ListNode * 型
        return dummy.next; // dummy 不是指针类型, ListNode 型
    }

    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l]; // 递归结束条件, [l, r]中 只剩下一个链表, l==r
        // if (l > r) return nullptr; // 只需要 一开始 特判 n 为 0
        int mid = (l + r) >> 1;
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        int n = lists.size();
        if (!n) return nullptr; // 特判 n == 0
        return merge(lists, 0, n - 1); // 不用特判 n 为 1
    }
};

wzc1995 2021-08-18 11:03

题目中没有写回收的逻辑，正常来说是需要在析构函数里手动delete的

Java 2021-06-24 12:55

学神

大风大雪 2021-06-22 12:04

真强！！！

Alexemey 2021-01-14 10:16

惊了

Omega_ 2020-02-26 21:07

学神！

Everglow 2019-11-14 22:08

请问一下分为左右部分时，
left = vector[HTML_REMOVED](lists.begin(), lists.begin() + mid);
right = vector[HTML_REMOVED](lists.begin() + mid, lists.end());
这两行代码中间链表不会比较两次吗？右边部分起始不该是mid+1吗？

wzc1995 2019-11-16 23:16

构造函数中的区间是左闭右开的，所以 left = vector<ListNode*>(lists.begin(), lists.begin() + mid); 是不包含 list.begin() + mid 的。

Everglow 2019-11-18 14:16 回复了 wzc1995 的评论

嗯嗯知道了，谢谢你！

Omega_ 2020-03-18 23:12 回复了 wzc1995 的评论

学神

wanting 2018-11-13 19:46

不对上面的复杂度写错了应该是：
1 + 2 +4 +…… + k/2 = k - 1
请问这样分析错在哪里了呢？谢谢！

wzc1995 2018-11-15 05:38

这里的 $n$ 指的是所有链表结点的个数，每一层遍历了所有结点，层数是 $\log⁡ k$，所以时间复杂度是 $O(n \log k)$。
如果你的 $n$ 指的是每个链表的最大个数，那确实需要 $O(nk)$ 的时间。

wanting 2018-11-15 14:28 回复了 wzc1995 的评论

原来 n 指的是所有链表的节点个数总和，我确实误以为单个链表的节点啦。谢谢你的分析！ :)

wanting 2018-11-13 19:40

请问为什么是logk复杂度呢？
列表里面有k个链表，假设k = 8，分别为1-8号链表；
1 与2合并一次得到新的链表（记为9）；
3与4合并一次得到10号；
5与6合并得到11；
7与8得到12；
接下来9与10 合并得到13；
11与12得到14；
最后13 14号合并得到最后的15；
这样应该是4 + 2 + 1 = 7才对呀（如果是logk的话就是log8 = 3)
复杂度不应该是 1 + 2 + 4 +……+ logk 吗？

App 内打开