STL priority_queue push 函数添加一个完整的链表 ( vector<ListNode*>& lists )，而不是一个元素

Question

出于自己的兴趣，我正在学习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) {}
 * };

Answer 1

有了那种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.

的函数