心之所向便是光

Leetcode 23.合并K个升序链表

  • 2021-06-02
  • 作者 Ender
  • 5.68K 字
  • 次阅读

题目描述：

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

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

示例 1：

1
2
3
4
5
6
7
8
9
10
输入：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：

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

示例 3：

1
2
输入：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$

链接：

https://leetcode-cn.com/problems/merge-k-sorted-lists

题目分析

  这道题是 Leetcode 21.合并两个有序链表 的升级版，原题链接以及相关题解都已经在这篇文章里面。

1. 顺序逐一合并

  根据我们对两个有序链表合并的思路，我们很容易想到，可以将其拆分成 k-1 个两链表合并的过程，逐一进行合并即可。代码中的 mergeTwoLists 函数即为合并两个有序链表的题解。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(-1);
        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }
        prev->next = l1?l1:l2;
        return preHead->next;
    }

public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return NULL;
        for(int i = 1; i < lists.size(); i++){
            lists[0] = mergeTwoLists(lists[0], lists[i]);
        }
        return lists[0];
    }
};

  时间复杂度：$O(k^2n)$，其中 $k、n$ 分别表示链表的数目和每个链表的长度。这是由于对于每一次合并时间复杂度都是两个链表的长度和，而对于第 $i$ 次合并 lists[0] 的长度应该为 $i\times n$，而 lists[i] 的长度为 $n$，一共需要合并 $k-1$ 次，则总的时间复杂度为 $O(\sum^{k-1}_{i=1}(i+1)\times n)=O(\frac{(k+2)(k-1)}{2}\times n)=O(k^2n)$。
  空间复杂度：$O(1)$。同两个链表合并，没有用到与 $k、n$ 规模相关的辅助空间。

2.分治合并

  从方法1中，我们可以发现，作为答案进行返回的 lists[0] 数组在每一次合并的时候都要遍历一次，这样的遍历是比较多余的，我们可以采用分治的思想进行优化。每一轮对每两条链表进行合并，得到 $\frac{k}{2}$ 条链表，然后再继续合并得到 $\frac{k}{4}$ 条链表，以此类推直到所有的链表合并完毕。下面所给的代码中已略去 mergeTwoLists 函数。

1
2
3
4
5
6
7
8
9
ListNode* merge(vector<ListNode*> &lists, int l, int r) {
    if (l == r) return lists[l];
    if (l > r) return nullptr;
    int mid = (l + r) / 2;
    return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
    return merge(lists, 0, lists.size()-1);
}

  时间复杂度：$O(kn\log k)$，其中 $k、n$ 分别表示链表的数目和每个链表的长度。对于第 $i$ 轮合并，每一条链表长度为 $2^{i-1}n$，则每一组合并的时间代价为 $O(2^in)$，一共有 $\displaystyle\frac{k}{2^i}$ 组。则总时间复杂度为 $O(\sum^{\infty}_{i=1}\frac{k}{2^i}\times2^in)=O(kn\log k)$。
  空间复杂度：$O(\log k)$，其中 $k$ 表示链表的数目。这是由于在分治合并中递归层数是 $\log k$。

3.K个链表一起合并

  类似于合并两个链表的双指针思路，我们可以直接使用k个指针分别指向k条链表，每一次合并时进行比较并将最小的加入到答案链表中。实际上这是我第一个想到的解法，然而这样的方法每一次加入都需要进行比较，每一次比较都必须遍历k条链表（即便为空也进行判断），并且没有任何剪枝，时间复杂度是非常高的，最后以 952ms 的运行时间勉强通过了测例。
  代码中的 flag 表示了当前是否获得第一个非空链表的头结点，这个结点值作为每一轮比较的初值；当所有的链表都为空时也即合并完毕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return NULL;
        ListNode *preHead = new ListNode(-1);
        ListNode *p = preHead;
        int min, min_index;
        bool flag = true;
        while(flag){
            flag = false;
            for(int i = 0; i < lists.size(); i++){
                if(lists[i] == NULL) continue;
                else{
                    if(!flag){
                        min = lists[i]->val;
                        min_index = i;
                        flag = true;
                    }
                    else if(lists[i]->val < min){
                        min = lists[i]->val;
                        min_index = i;
                    }
                }
            }
            if(flag){
                p->next = lists[min_index];
                p = p->next;
                lists[min_index] = lists[min_index]->next;
            }
        }
        return preHead->next;
    }
};

  时间复杂度：$O(k^2n)$，其中 $k、n$ 分别表示链表的数目和每个链表的长度。一共有 $kn$ 个结点需要进行添加，而每一次添加都需要对 $k$ 个链表的头结点进行遍历比较得到最小值，因此时间复杂度为 $O(k^2n)$。
  空间复杂度：$O(1)$。对于每一次添加我们只需要维护两个变量分别记录最小值以及最小值所在的链表。

4.合并后排序再连接

  简单粗暴的解法，直接按顺序读取所有的结点到数组中存放，然后对整个数组进行排序，之后再逐一连接起来。出乎意料的是，这样的运行时间其实蛮快的。真是暴力而又省事的解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
bool cmp(ListNode *a, ListNode *b){
    return a->val < b->val;
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> all;
        for(int i = 0; i < lists.size(); i++){
            ListNode *p = lists[i];
            while(p){
                all.push_back(p);
                p = p->next;
            }
        }
        if(all.size() == 0) return NULL;
        sort(all.begin(), all.end(), cmp);
        for(int i = 1; i < all.size(); i++){
            all[i-1]->next = all[i];
        }
        all[all.size()-1]->next = NULL;
        return all[0];
    }
};

  时间复杂度：$O(kn\log(kn))$，其中 $k、n$ 分别表示链表的数目和每个链表的长度。一共 $kn$ 个结点，将其逐一添加到数组中需要 $kn$ 的时间代价，而后进行排序我们认为是 $O(kn\log(kn))$ 的，其实他们已经相对有序，相当于已经进行了一部分的分治排序，sort 函数底层如果有实现相对于的优化的话实际耗时是比较短的。最后重连接的时候也需要 $kn$ 的时间代价。
  空间复杂度：$O(kn)$，其中 $k、n$ 分别表示链表的数目和每个链表的长度。我们开辟了一个新的数组用来存放 $kn$ 个结点。

本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可
,
最后编辑：2021-06-09