【leetcode】Merge k Sorted Lists

地址

https://leetcode.com/problems/merge-k-sorted-lists/description/ ## 题目 Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

思路

1.分治:很容易想到分治,就像一个二叉树从下往上跑 2.平衡树:既然想到了二叉树,那么用平衡树自然也可以。把所有的序列的值都插入到树上,然后一次性加到链表中。c++中用multiset替代。 3.优先队列/堆:这也是一个很基础的想法,每次从k个链表中取出一个最小值即可。这个方法的关键是如何在短时间内从k个链表中找出最小的那个,显然可以用优先队列or堆。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 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) {
multiset<int>st;
for(auto vc:lists)
for(ListNode* it=vc;it!=NULL;it=it->next)
st.insert(it->val);
ListNode *ret = new ListNode(0),*p = ret;
for(auto it=st.begin();it!=st.end();it++)
{
p->next = new ListNode(*it);
p=p->next;
}
return ret->next;
}
};