在之前的文章中分析过合并两个有序的链表，今天遇到一道题就是合并多个链表，则有分治法和优先队列的解法。
分治法
分治法的思想是，把一个复杂问题分解成两个或者更多相同或相似的子问题，再把子问题分成更小的子问题，直到最后的子问题可以简单地直接求解，最后把子问题的解合并，就得到原问题的解啦。（昨天百度一面的时候问过这个问题）
[ 1->4->5, 1->3->4, 2->6] 输出: 1->1->2->3->4->4->5->6
首先把容器中每一个链表通过 merge() 拆解，直到剩下一个个链表，再通过mergeTwoLinks()把相邻的链表进行有序合并。
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
| ListNode* mergeTwoLinks(ListNode* list1, ListNode* list2)* list1, ListNode* liists2)2{
if (!list1) {
return list2;
} else if (!list2) {
return list1;
} else if (list1->val < list2->val) {
list1->next = mergeTwoLinks(list1->next, list2);
return list1;
} else {
list2->next = mergeTwoLinks(list1, list2->next);
return list2;
}
}
ListNode* merge(vector<ListNode*>& lists, int left, int right){
if(left == right)
return lists[left];
int mid = (right + left) >> 1;
ListNode* l1 = merge(lists, left, mid);
ListNode* l2 = merge(lists, mid + 1, right);
return mergeTwoLinks(l1,l2);
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if(lists.size() == 0)
return NULL;
return merge(lists, 0, lists.size() - 1);
}
|
(实践证明，合并两链表的时候，用递归的方法比迭代的方法更优)
优先队列
参考LeetCode题解
我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 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
| class Solution {
public:
struct Status{
int val;
ListNode* ptr;
bool operator < (const Status &rhs) const{
return val > rhs.val;
}
};
priority_queue <Status> q;
ListNode* mergeKLists(vector<ListNode*>& lists) {
for (ListNode* node: lists) {
if (node) q.push({node->val, node});
}
ListNode head, *tail = &head;
while (!q.empty()) {
Status f = q.top(); q.pop();
tail->next = f.ptr;
tail = tail->next;
if (f.ptr->next) q.push({f.ptr->next->val, f.ptr->next});
}
return head.next;
}
};
|
