刀背我藏身
世路风波君自珍
C++，最小堆，链表排序。
这道题做了挺久的，主要是因为堆的实现都忘了，向上调整，向下调整。当然写起来代码也是挺长的，很复杂。这里我为了复习堆的实现，是直接写了一个MHeap类。
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<ListNode *> _heap;
};
这里实现了最小堆的插入和删除操作，这里稍微说一下：
- 堆的插入，插入至末尾，由下至上调整
- 堆的删除，首尾交换，由上至下调整
基本回忆回忆都能写出来，就是时间花得有点久。
用最小堆，思路会相当明朗。
- 首先将各个链表的第一个元素插入堆
- 进入循环，条件为堆不为空：
- 弹出堆顶指针，插入到要输出的链表里
- 如果堆顶指针的结点的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<ListNode *> _heap;
};
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*> &lists) {
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;
}
};
