【牛客227题解析】合并K个有序链表的优先队列解法（附代码）

一、题目解读

牛客227题要求合并K个有序链表，即将多个有序的单向链表合并成一个有序链表。题目考察的核心是对链表操作的熟练度以及高效算法的设计，通常需要平衡时间复杂度和空间复杂度，确保合并过程稳定且高效。

二、解题思路

采用优先队列（最小堆）实现合并。核心思想是：通过维护一个存放链表头节点的优先队列，每次取出队首（最小值节点），将其连接到结果链表，并继续将下一个节点加入队列，循环直至队列为空。这种方法能动态选择当前最小的节点，避免传统双指针法需要逐个比较的复杂度。

三、解题步骤

1. 创建优先队列：自定义比较函数（小顶堆），按节点值升序排序。

2. 初始化：遍历输入链表数组，将非空头节点加入队列。

3. 构建结果链表：使用哑节点（dummy）作为结果链表头，尾指针tail指向哑节点。

4. 循环合并：

○ 弹出队首节点minNode，将其连接到tail后，移动tail。

○ 若minNode有后继节点，则加入队列，确保后续节点参与比较。

5. 返回哑节点的下一个节点（即实际结果链表头）。

四、代码和注释

#include <vector>
#include <queue>
using namespace std;

// 自定义优先队列比较函数（小顶堆）
struct cmp {
    bool operator()(ListNode* a, ListNode* b) {
        return a->val > b->val; // 按值升序排列（小顶堆）
    }
};

class Solution {
  public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 1. 创建优先队列（最小堆）
        priority_queue<ListNode*, vector<ListNode*>, cmp> minHeap;

        // 2. 将所有链表的头节点加入堆中
        for (auto list : lists) {
            if (list!= nullptr) { // 过滤空链表
                minHeap.push(list);
            }
        }

        // 3. 创建哑节点作为结果链表的起始点
        ListNode dummy(0);
        ListNode* tail = &dummy;

        // 4. 不断从堆中取出最小节点，连接到结果链表
        while (!minHeap.empty()) {
            // 取出当前最小节点
            ListNode* minNode = minHeap.top();
            minHeap.pop();

            // 将该节点连接到结果链表
            tail->next = minNode;
            tail = tail->next;

            // 若该节点有后继，加入堆中
            if (minNode->next!= nullptr) {
                minHeap.push(minNode->next);
            }
        }

        return dummy.next; // 返回结果链表头
    }
};

五、总结

本解法通过优先队列优化了多链表合并的逻辑，将时间复杂度控制在O(NlogK)（N为总节点数，K为链表数量），空间复杂度为O(K)。相较于传统方法，其优势在于动态选择最小节点，适用于大规模链表合并场景。在编程面试中，该思路能体现对数据结构的灵活应用，是解决此类问题的经典策略。