题解 | 合并k个已排序的链表

/**
 * struct ListNode {
 *  int val;
 *  struct ListNode *next;
 *  ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
//方法一：使用priority_queue（推荐）
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param lists ListNode类vector
     * @return ListNode类
     */
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
// 自定义比较函数，创建最小堆
        // 1. 定义 lambda 比较函数
        auto cmp = [](ListNode * a, ListNode * b) {
            return a->val > b->val; // 注意：这里用 > 创建最小堆
        };
	  // 2. 使用 decltype 获取 cmp 的类型
    // decltype(cmp) 推导出 lambda 的类型
	  //lambda表达式没有默认构造函数，必须在构造时传入具体的比较器对象
        priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> minHeap(cmp);

        // 将所有链表的头节点加入最小堆
        for (ListNode* node : lists) {
            if (node != nullptr) {
                minHeap.push(node);
            }
        }

        ListNode dummy(0); // 哑节点
        ListNode* current = &dummy;

        while (!minHeap.empty()) {
            // 取出当前最小节点
            ListNode* minNode = minHeap.top();
            minHeap.pop();

            current->next = minNode;
            current = current->next;

            // 如果该节点还有下一个节点，加入堆中
            if (minNode->next != nullptr) {
                minHeap.push(minNode->next);
            }
        }

        return dummy.next;
    }
};
//方法二：使用函数对象作为比较器
// 比较器类
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> minHeap;
        
        for (ListNode* node : lists) {
            if (node != nullptr) {
                minHeap.push(node);
            }
        }
        
        ListNode dummy(0);
        ListNode* current = &dummy;
        
        while (!minHeap.empty()) {
            ListNode* minNode = minHeap.top();
            minHeap.pop();
            
            current->next = minNode;
            current = current->next;
            
            if (minNode->next != nullptr) {
                minHeap.push(minNode->next);
            }
        }
        
        return dummy.next;
    }
};