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

  |  

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

本题有两个主流解法:

算法1:堆
算法2:分治

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

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

下面我们看一下这个题

$1 题目

题目链接

23. 合并K个升序链表

题目描述

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

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

样例

示例 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 个链表最小元素中的最小的,归并后链表的下一个元素即为堆顶元素,将堆头出堆,并将堆头对应的链表节点的下一节点进堆,如果没有下一节点则跳过。

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

时间复杂度 $O(N\log K)$

代码

  • 自定义比较的方法1:定义结构体,里面只重载 ()
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
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); // > 是小顶堆;< 是大顶堆
}
};
};
  • 自定义比较的方法法二
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
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,可以直接解决,将链表直接返回即可
  • 合并:将两个有序链表归并成一个

时间复杂度:$O(N\log 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
33
34
35
36
37
38
39
40
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;
}
};

代码:自底向上

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
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;
}
};

Share