LeetCode merge-k-sorted-lists

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

输入: [ 1->4->5, 1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6

解答:

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
class Solution {
public:
// 优先队列,最小堆
ListNode* mergeKLists1(vector<ListNode*>& lists) {
ListNode res{0}, *cur = &res;
auto cmp = [](const ListNode *a, const ListNode *b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)>heap(cmp);
for (ListNode *node : lists) if (node) heap.push(node);
while (!heap.empty()) {
ListNode *tmp = heap.top();
heap.pop();
cur->next = tmp;
cur = cur->next;
if (tmp->next) heap.push(tmp->next);
}
return res.next;
}

// 暴力法,将所有链表节点取出排序
ListNode* mergeKLists2(vector<ListNode*>& lists) {
ListNode res{0}, *cur = &res;
vector<int> data;
for(ListNode *node : lists) {
while(node) {
data.push_back(node->val);
node = node ? node->next : nullptr;
}
}
sort(data.begin(), data.end());
for(int i : data) {
cur->next = new ListNode {i};
cur = cur->next;
}
return res.next;
}

// 归并分治
ListNode* mergeKLists3(vector<ListNode*>& lists) {
int len = lists.size(), gap = 1;
while (gap < len) {
for (int i = 0; i < len - gap; i += gap * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + gap]);
}
gap *= 2;
}
if (lists.size() > 0) return lists[0];
return lists;
}

// 双端队列,每次合并两个
ListNode* mergeKLists4(vector<ListNode*>& lists) {
ListNode res{0}, *cur = &res;
deque<ListNode*> head;
for (auto node : lists) {
if (node)
head.push_back(node);
}
if(!head.size()) return nullptr;
ListNode *p1, *p2;
while (head.size() != 1) {
p1 = head.back();
head.pop_back();
p2 = head.back();
head.pop_back();
head.push_front(mergeTwoLists(p1, p2));
}
return head.back();
}

// 合并两个有序链表方法
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode res {0};
ListNode *tmp = &res;

while (l1 && l2) {
if (l1->val <= l2->val) {
tmp->next = new ListNode{l1->val};
l1 = l1 ? l1->next : nullptr;
} else {
tmp->next = new ListNode{l2->val};
l2 = l2 ? l2->next : nullptr;
}
tmp = tmp->next;
}
l1 ? tmp->next = l1 : tmp->next = l2;
return res.next;
}
};

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×