Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
题解：
归并思想。
Solution 1
/**
* 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) {
int n = lists.size();
if (n < )
return nullptr; for (int i = ; i < n ; i *= ) {
int len = i;
for (int j = ; j + len < n; j += *len) {
lists[j] = mergeTwoLists(lists[j], lists[j + len]);
}
} return lists[];
}
ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
ListNode dummy(-);
ListNode *cur = &dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
cur->next = l1 ? l1 : l2; return dummy.next;
}
};
Solution 2
利用最小堆，c++的优先队列priority_queue。
class Solution {
public:
struct cmp {
bool operator () (ListNode *a, ListNode *b) {
return a->val > b->val;
}
};
ListNode *mergeKLists(vector<ListNode *> &lists) {
priority_queue<ListNode*, vector<ListNode*>, cmp> q;
for (auto list : lists) {
if (list)
q.push(list);
}
ListNode *head = NULL, *pre = NULL, *tmp = NULL;
while (!q.empty()) {
tmp = q.top();
q.pop();
if (!pre)
head = tmp;
else
pre->next = tmp;
pre = pre->next;
// 此节点所在数组仍有元素，则添加进最小堆中
if (tmp->next)
q.push(tmp->next);
}
return head;
}
};
转自：Grandyang