力扣题目解析--合并k个升序链表

题目

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下：
[
  1->4->5,
  1->3->4,
  2->6
]
将它们合并到一个有序链表中得到。
1->1->2->3->4->4->5->6

示例 2：

输入：lists = []
输出：[]

示例 3：

输入：lists = [[]]
输出：[]

提示：

• k == lists.length
• 0 <= k <= 10^4
• 0 <= lists[i].length <= 500
• -10^4 <= lists[i][j] <= 10^4
• lists[i] 按 升序 排列
• lists[i].length 的总和不超过 10^4

代码展示 

#include <queue>
using namespace std;

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // 最小堆
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, Compare> pq;
        
        
        for (auto& list : lists) {
            if (list) {
                pq.push(list);
            }
        }
        
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        
        while (!pq.empty()) {
            ListNode* top = pq.top();
            pq.pop();
            
            current->next = top;
            current = current->next;
            
            if (top->next) {
                pq.push(top->next);
            }
        }
        
        return dummy->next;
    }
};

写者心得 

练习中曾经做过合并两个链表的题，然后写者准备加一个循环，就是把他给的这个数组里面的链表提取出来之后再合并起来，但是运行出了bug，于是我就去找到了这样一个和我当初思路截然不同的做法，这个利用的是栈，代码比我当初利用for循环来进行链表合并要少很多

逐行解析

1. 自定义比较器：

   struct Compare {
       bool operator()(ListNode* a, ListNode* b) {
           return a->val > b->val; // 最小堆
       }
   };

   • 这是一个自定义的比较器，用于优先队列中的排序。
   • operator() 定义了比较规则，使得优先队列成为一个最小堆，即队列顶部的节点值是最小的。

2. 创建优先队列：

   priority_queue<ListNode*, vector<ListNode*>, Compare> pq;

   • 使用 priority_queue 创建一个最小堆，存储类型为 ListNode*。
   • vector<ListNode*> 是优先队列的底层容器。
   • Compare 是自定义的比较器，确保优先队列按节点值从小到大排序。

3. 初始化优先队列：

   for (auto& list : lists) {
       if (list) { // 检查链表是否为空
           pq.push(list);
       }
   }

   • 遍历输入的链表列表 lists。
   • 对于每个链表，检查其是否为空（if (list)），如果不为空，则将其头节点加入优先队列。

4. 创建虚拟头节点：

   ListNode* dummy = new ListNode(0);
   ListNode* current = dummy;

   • 创建一个虚拟头节点 dummy，值为 0。
   • current 指向 dummy，用于构建新的链表。

5. 合并链表：

   while (!pq.empty()) {
       ListNode* top = pq.top();
       pq.pop();
       
       current->next = top;
       current = current->next;
       
       if (top->next) {
           pq.push(top->next);
       }
   }

   • 当优先队列不为空时，进入循环。
   • 从优先队列中取出当前最小的节点 top。
   • 将 top 添加到新链表中，即 current->next = top，并移动 current 到 top。
   • 如果 top 有下一个节点（if (top->next)），则将 top->next 加入优先队列。

6. 返回新链表的头节点：

   return dummy->next;

   • 返回新链表的头节点，即 dummy 的下一个节点。

条件的使用

• if (list)：检查链表是否为空。只有非空链表的头节点才会被加入优先队列。
• if (top->next)：检查当前节点是否有下一个节点。如果有，则将下一个节点加入优先队列，以继续参与后续的合并操作。

1. 自定义比较器

什么是比较器？

比较器是一个函数对象，用于定义两个对象之间的比较规则。在 C++ 标准库中，许多容器（如 std::sort、std::priority_queue）都允许用户自定义比较器。

自定义比较器的例子

struct Compare {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // 最小堆
    }
};

• struct Compare：定义一个结构体 Compare，用于存储比较逻辑。
• bool operator()(ListNode* a, ListNode* b)：重载 () 操作符，使其像一个函数一样调用。
  • 参数 a 和 b 是两个 ListNode* 类型的指针。
  • 返回值 bool 表示 a 是否大于 b。
  • return a->val > b->val;：如果 a 的值大于 b 的值，返回 true，否则返回 false。这使得优先队列成为一个最小堆。

2. 创建优先队列

什么是优先队列？

优先队列是一种特殊的队列，取出元素的顺序并不是按照进入的顺序，而是根据元素的优先级。在 C++ 中，std::priority_queue 是一个容器适配器，默认情况下是一个最大堆（即队列顶部的元素是最大的）。

创建最小堆的优先队列

priority_queue<ListNode*, vector<ListNode*>, Compare> pq;

• priority_queue<ListNode*, vector<ListNode*>, Compare>：
  • 第一个模板参数 ListNode*：优先队列中存储的元素类型。
  • 第二个模板参数 vector<ListNode*>：底层容器，用于存储元素。默认情况下是 vector。
  • 第三个模板参数 Compare：自定义的比较器，用于定义元素的优先级