Merge k sorted linked lists and return it as one sorted list.
Analyze and describe its complexity.
每次遍历找范围内最小,用min heap。每次找到最小pop后再把最小的next push进去作为候选。C++的pq 用greater作为comparator才是min heap,和Java的相反。。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
for (int i = 0; i < lists.length; i++) {
if (lists[i] != null) {
pq.offer(lists[i]);
}
}
ListNode dummy = new ListNode(0), node = dummy;
while (!pq.isEmpty()) {
ListNode newNode = pq.poll();
node.next = newNode;
node = newNode;
if (newNode.next != null) {
pq.offer(newNode.next);
}
}
return dummy.next;
}
}
/*
* @lc app=leetcode id=23 lang=cpp
*
* [23] Merge k Sorted Lists
*/
/**
* 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) {
const auto cmp = [](ListNode *a, ListNode *b) {
return (a->val) > (b->val);
};
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
for (const auto node : lists) {
if (node != nullptr) pq.push(node);
}
ListNode *dummy = new ListNode(-1), *cur = dummy;
while (!pq.empty()) {
const auto t = pq.top(); pq.pop();
cur->next = t;
cur = cur->next;
if (t->next != nullptr) pq.push(t->next);
}
cur->next = nullptr;
return dummy->next;
}
};