leetcode题记 23.合并K个有序链表

题目

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[1->4->5, 1->3->4, 2->6]

输出: 1->1->2->3->4->4->5->6

来源:力扣(LeetCode)

题解

这道题一共有5种官方解法,每种解法都对应不同的水平。
分别是:

  1. 暴力遍历法
  2. 逐一比较法
  3. 优先队列法
  4. 逐一合并法 & 分治+合并法

暴力遍历法

暴力遍历法思想很简单,即为多个链表转化为一个数组,对数组进行排序后再将数组转化为链表。因为链表转化为数组是O(N),而数组转化为链表也是O(N),所以我觉得这里头影响最大的就是排序算法。

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
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
vector<int> arr;
int k = lists.size();
for (int i = 0; i < k; i++) {
ListNode *p = lists[i];
while (p != nullptr) {
arr.push_back(p->val);
p = p->next;
}
}

sort(arr.begin(), arr.end());

ListNode head(-1), *p;
p = &head;
for (int i = 0; i < arr.size(); i++) {
p->next = new ListNode(arr[i]);
p = p->next;
}
return head.next;
}
};

执行用时 : 32 ms, 在所有 C++ 提交中击败了97.09%的用户
内存消耗 :11.6 MB, 在所有 C++ 提交中击败了67.33%的用户

逐一合并法 & 分治+合并法

逐一合并法,即按照顺序将第1个链表与之后的每个链表合并。需要用到之前写过的合并两个有序链表的方法作为核心合并算法,并且合并算法的快慢差距在这题里面更加的放大了。由于逐一合并法和分治合并法对链表的合并次数都相同,而逐一合并法的算法分析结果是O(kN)(N为总节点数),而分治法的算法分析结果是O(NlogN)。所以选取分治合并法。

其中k和logN的差距点在于,逐一合并法里面,对于已经合并排序过的节点在之后的合并排序中都会排序一次,而分治合并则在前面第一趟分治中有没重复运算的节点,所以就更加的节约了时间。

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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
* 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(0);
register ListNode *o = &head;
while (l1 && l2) {
if (l1->val <= l2->val) {
o->next = l1;
l1 = l1->next;
} else {
o->next = l2;
l2 = l2->next;
}
o = o->next;
}
if (l1) {
o->next = l1;
} else if (l2) {
o->next = l2;
}
return head.next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
register int step = 1, k = lists.size();

if (k == 0) {
return NULL;
} else if (k == 1) {
return lists[0];
} else if (k == 2) {
return merge2Lists(lists[0], lists[1]);
}

while (step < k) {
for (int i = 0; i < k-step; i+=step*2) {
lists[i] = merge2Lists(lists[i], lists[i+step]);
}
step *= 2;
}
return lists[0];
}
};

执行用时 :32 ms, 在所有 C++ 提交中击败了97.12%的用户
内存消耗 : 10.7 MB, 在所有 C++ 提交中击败了98.35%的用户

Author: SmallXeon
Link: https://hexo.chensmallx.top/2019/07/30/leetcode-23-mergeKLists/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.
一些推广链接
几个便宜量大的小✈场: FASTLINK, YToo, 论坛邀请注册: ,
便宜量大但是稳定性不足的VPS: , 价格略贵但好用的VPN: , ,