未为链表中的所有元素调用优先级队列比较器

priority queue comparator not called for all the elements in the linked list

提问人:BEPP 提问时间:9/2/2023 更新时间:9/2/2023 访问量:22

问:

我正在努力使用 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
c++ 优先级队列

评论

1赞 Pepijn Kramer 9/2/2023
首先建议,停止做 leetcode 谜题,先学习更多 C++ 。并使用本地开发环境和调试器来执行此操作。(请注意,leetcode 甚至没有使用 std::list,这应该表明他们对 C++ 不感兴趣,只是对你生成的算法感兴趣)。此外,您的代码正在泄漏内存
0赞 fabian 9/2/2023
你是否总是在代码中使用这种令人困惑的意图?不?然后,请体谅您寻求帮助的人,并确保您发布的代码没有这些与实际问题完全无关的问题。
1赞 Igor Tandetnik 9/3/2023
您的算法假定传递给它的每个列表都已排序。但是您传递的其中一个列表实际上没有排序。
0赞 BEPP 9/3/2023
@IgorTandetnik感谢您指出问题。:)

答: 暂无答案