Leetcode23
题目描述
- Merge k Sorted Lists Solved Hard Topics premium lock icon Companies You are given an array of k linked-lists lists, each linked-list is sorted in ascending order.
Merge all the linked-lists into one sorted linked-list and return it.
思路
简单的合并这些链表即可，优化方案是采用map维护这个谁先谁后的问题。
代码
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
map<int, vector<ListNode*>> map;
for (auto& l : lists) {
if (l == nullptr) continue;
if (map.find(l->val) != map.end()) {
map[l->val].push_back(l);
}
else {
map[l->val] = vector<ListNode*>({ l });
}
}
ListNode* res = new(nothrow) ListNode;
if (res == nullptr) return res;
ListNode* pr = nullptr;
while (!map.empty()) {
if (pr != nullptr) {
pr->next = new(nothrow) ListNode;
if (pr == nullptr) return nullptr;
pr = pr->next;
}
else {
pr = res;
}
pr->val = map.begin()->first;
ListNode* tmp = map.begin()->second.back();
if (map.begin()->second.size() == 1) {
map.erase(tmp->val);
}
else {
map.begin()->second.pop_back();
}
if (tmp->next == nullptr) continue;
else {
if (map.find(tmp->next->val) != map.end()) {
map[tmp->next->val].push_back(tmp->next);
}
else {
map[tmp->next->val] = vector<ListNode*>({ tmp->next });
}
}
}
if (pr != nullptr)
pr->next = nullptr;
else{
delete res;
res=nullptr;
}
return res;
}
};