时间戳

首页 > 解决方案 > STL priority_queue push 函数添加一个完整的链表（向量& 列表），而不是一个元素

c++ - STL priority_queue push 函数添加一个完整的链表（向量& 列表），而不是一个元素

问题描述

我出于自己的兴趣学习 C++。我遇到了一个我无法从逻辑上理解的情况。

我正在尝试解决这个问题：https ://leetcode.com/problems/merge-k-sorted-lists/ ，在 Min Heap 的帮助下。我将优先级队列用作最小堆。

现在我的代码看起来像这样：

 ListNode* mergeKLists(vector<ListNode*>& lists) {
     struct Compare {
                    bool operator() (const ListNode *a, const ListNode *b) {
                        return a->val > b->val;
                    }
                };
        
        
        
                
        // Use min heap to keep the smallest node of each list
                priority_queue<ListNode *, vector<ListNode *>, Compare> min_heap;
                for (auto n : lists) {
                    if(n){
                        min_heap.push(n);
                    }
                    
                }
.
.
.
.
}

我得到了正确的输出。

该代码 min_heap.push(n);正在推动 min_heap 中的整个链表，我不确定为什么会发生这种情况。

它应该只将链表的第一个元素推入 min_heap 。对 ？

请告诉我。

节点的结构如下所示：

struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };

标签： c++linked-listpriority-queue

解决方案

使用这种Node数据结构，对您的第一个节点的引用也是对您的链表的引用，因为第一个节点next指向第二个，然后next->next将指向第三个......等等。所以它的行为符合预期.

当前行为

在执行 for 循环之后，您将拥有每个链表的第一个元素的队列（其中还包含指向链表其余部分的指针，但不包含在队列中）按值排序。检查它的大小，你会看到。

预期行为

对于我在练习中看到的内容，您不仅需要插入每个链表的第一个节点，还需要插入所有节点，因此您应该创建一个嵌套的 for 循环来为每个链表添加每个节点：

for (auto n : lists){ // for every list
  ListNode* iterator = n;
  // I assume that your last element in each list has next pointing to null
  while(iterator) { // add all the nodes
    min_heap.push(iterator);
    iterator = iterator->next;
  }
}

这会将列表中的每个节点分别添加到队列中。

重要提示：如果您使用打印链表的函数，您会在这里看到很多重复，原因与您在第一次尝试时看到整个链表的原因相同。要准确查看队列中存储了哪些节点，您必须使用一个仅打印节点值且不使用next.

推荐阅读