问题：给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
C++，最小堆，链表排序
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
class MHeap {public:
MHeap(uint64_t k) {
_heap.reserve(k);
}
void insertx(ListNode *nodep) {
}
void pop() {
}
ListNode *top() {
return _heap[0];
}
bool empty() {
return _heap.empty();
}
private:
vector
};
这里实现了最小堆的插入和删除操作，这里稍微说一下：堆的插入，插入至末尾，由下至上调整；堆的删除，首尾交换，由上至下调整
用最小堆，思路会相当明朗。
- 首先将各个链表的第一个元素插入堆
- 进入循环，条件为堆不为空：
- 弹出堆顶指针，插入到要输出的链表里
- 如果堆顶指针的结点的next指针不为空，将next指针压入最小堆
- 继续循环
需要注意的是lists中可能会有空指针。
题目中说到了要分析时间复杂度和空间复杂度，时间复杂度：O(NlogK)；空间复杂度：O(K)。
代码：
class MHeap {public:
MHeap(uint64_t k) {
_heap.reserve(k);
}
void insertx(ListNode *nodep) {
_heap.emplace_back(nodep);
uint64_t child = _heap.size() - 1;
while (child > 0) {
uint64_t pa = (child - 1) / 2;
child = pa * 2 + 1;
if (child + 1 < _heap.size())
child = _heap[child]->val <= _heap[child + 1]->val ? child : child + 1;
if (_heap[child]->val < _heap[pa]->val)
swap(_heap[child], _heap[pa]);
else break;
child = pa;
}
}
void pop() {
swap(_heap[0], _heap[_heap.size() - 1]);
_heap.pop_back();
uint64_t pa = 0, child = 1;
while (pa * 2 + 1 < _heap.size()) {
child = pa * 2 + 1;
if (child + 1 < _heap.size())
child = _heap[child]->val <= _heap[child + 1]->val ? child : child + 1;
if (_heap[child]->val < _heap[pa]->val)
swap(_heap[child], _heap[pa]);
else break;
pa = child;
}
}
ListNode *top() {
return _heap[0];
}
bool empty() {
return _heap.empty();
}
private:
vector
};
class Solution {public:
ListNode* mergeKLists(vector
if (lists.empty()) return nullptr;
MHeap heap(lists.size());
for (auto &it : lists) {
if (it)
heap.insertx(it);
}
ListNode *dummy = new ListNode(0), *p = dummy;
while (!heap.empty()) {
ListNode *temp = heap.top();
heap.pop();
p->next = temp;
if (temp->next)
heap.insertx(temp->next);
p = p->next;
}
return dummy->next;
}
};
