提问人:BEPP 提问时间:9/2/2023 更新时间:9/2/2023 访问量:22
未为链表中的所有元素调用优先级队列比较器
priority queue comparator not called for all the elements in the linked list
问:
我正在努力使用 pq 合并 K 链表。但是比较器不适用于链表中的所有元素。有人请说明为什么比较器无法按预期工作。
如果所有链表只有一个节点,则此代码有效。不知道为什么比较器不适用于下一个节点。
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
class ListNode {
public:
int val;
ListNode *next;
ListNode() {
this->val = 0;
this->next = nullptr;
}
ListNode(int x) {
this->val = x;
this->next = nullptr;
}
ListNode(int x, ListNode *next):val(x),next(next) {
}
};
class Solution {
public:
struct cmp {
bool operator()(ListNode *a, ListNode *b) {
return a->val > b->val;
}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
priority_queue<ListNode *, vector<ListNode*>, cmp> pq;
ListNode *dummy = new ListNode(0);
ListNode *cur = dummy;
ListNode *top;
for (int i=0; i< lists.size(); i++) {
pq.push(lists[i]);
}
while(!pq.empty()) {
top = pq.top();
pq.pop();
cur->next = top;
cur = cur->next;
cur->next = nullptr;
if(top->next != nullptr) {
pq.push(top->next);
}
}
return dummy->next;
}
};
int main() {
Solution obj;
ListNode *a = new ListNode(9);
a->next = new ListNode(34);
a->next->next = new ListNode(55);
ListNode *b = new ListNode(45);
b->next = new ListNode(4);
b->next->next = new ListNode(5);
vector<ListNode*> Lists;
Lists.push_back(a);
Lists.push_back(b);
ListNode *result = obj.mergeKLists(Lists);
while(result != nullptr) {
cout<<result->val<< " ";
result = result->next;
}
cout<<endl;
return 0;
}
输出:
9 34 45 4 5 55
答: 暂无答案
评论