LeetCode Merge k Sorted Lists 题解

LeetCode Merge k Sorted Lists 题解

思路一

使用之前合并两个lists的方法,重复调用k次

思路二

从lists中找到前面一个元素最小的list,将这个list的首个node加入到要返回的list中的末尾中去,不断循环,直到lists中所有的node都取出来为止

代码:

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
51
52
53
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
int getMinIndex(vector<ListNode*>& lists)
{
int minVal = 2147483647 ,minIndex = -1;
for(int i=0;i<lists.size();i++)
{
if(lists[i] != NULL && minVal > lists[i]->val)
{
minVal = lists[i]->val;
minIndex = i;
}
}
return minIndex;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode* res =NULL, *p =NULL;
int len = lists.size();
if(len == 0) return NULL;
int ind = getMinIndex(lists);
while(ind != -1)
{
// node 移植
if(res ==NULL)
{
res = p = lists[ind];
}
else
{
p->next = lists[ind];
p = p->next;
}
// 删除list中的node
lists[ind] = lists[ind]->next;
ind = getMinIndex(lists);
}
return res;
}
};

思路三

将所有的node都加入到一个最小堆中,不断从这个最小堆中取出最小的一个node形成一个list

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
/**
* 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) {
ListNode dummy(0);
auto *cur = &dummy;
struct Compare {
bool operator() (const ListNode *a, const ListNode *b) {
return a->val > b->val;
}
};
// Use min heap to keep the smallest node of each list
priority_queue<ListNode *, vector<ListNode *>, Compare> min_heap;
for (const auto& n : lists) {
if (n) {
min_heap.emplace(n);
}
}
while (!min_heap.empty()) {
// Get min of k lists.
auto *node = min_heap.top();
min_heap.pop();
cur->next = node;
cur = cur->next;
if (node->next) {
min_heap.emplace(node->next);
}
}
return dummy.next;
}
};

思路四

归并排序的思想,不断拆分成两个list的合并,最后合并的次数只有logk次,所以整体的时间复杂为O(n*logk)

更多LeetCode题解,欢迎查看我的GitHub项目