class Solution {
public:
ListNode* merge2Lists(ListNode* l1, ListNode* l2) {
auto prehead = new ListNode();
auto merge = prehead;
while (l1 || l2) {
if (!l1) {
merge->next = l2;
break;
} else if (!l2) {
merge->next = l1;
break;
} else if (l1->val <= l2->val) {
merge->next = new ListNode(l1->val);
l1 = l1->next;
} else if (l1->val > l2->val) {
merge->next = new ListNode(l2->val);
l2 = l2->next;
}
merge = merge->next;
}
return prehead->next;
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
if (lists.empty()) return nullptr;
if (lists.size() == 1) return lists[0];
auto mergeList = merge2Lists(lists[0], lists[1]);
for (int i = 2; i < lists.size(); i++)
mergeList = merge2Lists(mergeList, lists[i]);
return mergeList;
}
};
class cmp {
public:
bool operator()(const ListNode* a, const ListNode* b) {
return a->val > b->val;
}
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
// 1.创建小根堆
priority_queue<ListNode*, vector<ListNode*>, cmp> q;
auto reshead = new ListNode(); // 返回结果的链表头
auto node = reshead;
// 2.把K个链表的非空头结点依次放入小根堆中
for (auto& head : lists)
if (head) q.push(head);
// 3.依次取出堆中最小链表节点
while (!q.empty()) {
auto tmp = q.top(); q.pop();
if (tmp->next) q.push(tmp->next); // 若该节点还有next节点,则压入堆中
node->next = tmp; // 堆中最小链表节点加入res
node = node->next; // 结果链表指针后移1位
}
return reshead->next;
}
};