牛客227 算法面试必刷题合并K个有序链表的完整剖析

6个月前 (06-03)牛客题解205

一、问题理解

首先，我们需要明确什么是"合并K个有序链表"。给定K个已经按升序排列的链表，我们需要将它们合并成一个新的有序链表。这个问题是经典"合并两个有序链表"问题的扩展，在数据处理、数据库操作等场景中非常常见。

二、解决方案分析

优先队列法：

我们使用优先队列（最小堆）来优化合并过程，这也是上面代码采用的方法。其核心思想是：

每次从K个链表的当前头节点中选出最小的节点
将该节点加入结果链表
将该节点的下一个节点加入比较范围
重复上述过程直到所有节点处理完毕

这种方法的时间复杂度是O(NlogK)，空间复杂度是O(K)。

三、完整代码

#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) {
        // 创建一个优先队列（最小堆）
        priority_queue<ListNode*, vector<ListNode*>, cmp> minHeap;
        
        // 1. 将所有链表的头节点加入堆中
        for (auto list : lists) {
            if (list != nullptr) {
                minHeap.push(list);
            }
        }
        
        // 2. 创建一个哑节点(dummy)作为结果链表的起始点
        ListNode dummy(0);
        ListNode* tail = &dummy;
        
        // 3. 不断从堆中取出最小节点，连接到结果链表
        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;
    }
};

四、代码逐行解析

让我们详细解析提供的C++代码：

1.自定义比较函数

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

定义了一个比较结构体，用于优先队列的比较。这里使用">"来创建最小堆。

2.核心合并函数

ListNode* mergeKLists(vector<ListNode*>& lists)

函数接收一个链表数组作为输入，返回合并后的链表头节点。

3.初始化优先队列

priority_queue<ListNode*, vector<ListNode*>, cmp> minHeap;

创建了一个最小堆，用于高效获取当前最小节点。

4.填充初始堆

for (auto list : lists) {
    if (list != nullptr) {
        minHeap.push(list);
    }
}

将所有非空链表的头节点加入堆中。

5.创建结果链表

ListNode dummy(0);
ListNode* tail = &dummy;

使用哑节点技巧简化链表操作，tail指针用于跟踪结果链表的末尾。

6.合并过程

while (!minHeap.empty()) {
    ListNode* minNode = minHeap.top();
    minHeap.pop();
    
    tail->next = minNode;
    tail = tail->next;
    
    if (minNode->next != nullptr) {
        minHeap.push(minNode->next);
    }
}