C++合并K个有序链表

本篇博客介绍如何使用C++合并k个有序链表，在代码中会用到std::priority_queue，首先需要介绍一下std::priority_queue的用法，介绍完std::priority_queue后将介绍如何使用std::priority_queue来辅助合并k个有序链表。

一、C++ priority_queue用法介绍

1.1 priority_queue基本用法

C++ 中的 priority_queue 是标准模板库（STL）中的一种数据结构，它是一个基于堆（默认为最大堆）的实现，用于自动排序插入的元素。在 priority_queue 中，元素被按优先级取出，这意味着最大的元素总是第一个被取出（如果你想要一个最小堆，你需要在声明时指定比较函数）。

priority_queue 在 <queue> 头文件中定义，通常用于需要按特定顺序处理元素的场景，如任务调度、带权路径搜索（如 Dijkstra 算法）等。

下面是一些 priority_queue 的基本用法示例：

包含头文件和创建 priority_queue

#include <iostream>
#include <queue>

int main() {
    // 默认是一个最大堆
    std::priority_queue<int> pq;

    // 创建一个最小堆，需要提供比较函数
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;

    return 0;
}

向 priority_queue 添加元素

pq.push(30);
pq.push(20);
pq.push(50);
pq.push(40);

访问 priority_queue 的顶部元素

std::cout << "The top element is: " << pq.top() << std::endl; // 输出最大元素，此处为 50

移除 priority_queue 的顶部元素

pq.pop(); // 移除最大元素，此处为 50

检查 priority_queue 是否为空

if (pq.empty()) {
    std::cout << "The priority queue is empty." << std::endl;
} else {
    std::cout << "The priority queue is not empty." << std::endl;
}

获取 priority_queue 的大小

std::cout << "The priority queue size is: " << pq.size() << std::endl;

1.2 priority_queue使用自定义类型

如果你想在 priority_queue 中使用自定义类型，则需要定义比较方式。例如，如果你有一个结构体 Point 并希望根据点的距离原点的远近来排序，可以这样做：

#include <queue>
#include <vector>
#include <iostream>

struct Point {
    double x, y;
    Point(double _x, double _y) : x(_x), y(_y){}    
    double distance() const { return x * x + y * y; }
};

// 定义比较函数
struct Compare {
    bool operator()(const Point& a, const Point& b) {
        return a.distance() < b.distance(); // 更远的点优先级更高
    }
};

int main() {
    std::priority_queue<Point, std::vector<Point>, Compare> pq;

    pq.push(Point(1, 2));
    pq.push(Point(3, 4));
    pq.push(Point(0, 0));

    while (!pq.empty()) {
        Point top = pq.top();
        std::cout << "Point with highest priority (farthest): (" << top.x << ", " << top.y << ")" << std::endl;
        pq.pop();
    }

    return 0;
}

在这个例子中，我们定义了一个比较结构体 Compare，它重载了 () 运算符来允许 priority_queue 判断哪个点应该先出列。这里我们让距离原点更远的点有更高的优先级。

1.3 问题 std::priority_queue<Point, std::vector, Compare> pq;为什么要填3个参数

在C++中，std::priority_queue是一个容器适配器，它提供常数时间的最大元素查找，以及对数时间的插入与删除。std::priority_queue默认使用std::vector作为其底层容器，并使用std::less作为比较函数来构造一个最大堆。

在你的例子中：

std::priority_queue<Point, std::vector<Point>, Compare> pq;

这里的三个参数分别是：

1. Point: 这是队列中要存储的元素类型。
2. std::vector<Point>: 这指定了底层容器类型。在这里是std::vector，它将被用来存储Point类型的元素。
3. Compare: 这是一个比较类（或者函数对象），用于定义优先队列中元素的优先级。

Compare参数需要是一个可以比较两个Point对象的函数或者函数对象。在std::priority_queue中，这个比较函数决定了队列中元素的排序方式。具体地，Compare定义了一个严格的弱序，当你想要从队列中取出元素时，队列会根据这个比较函数给出的优先级，提供最"高"优先级的元素。

默认情况下，如果不提供Compare类型，std::priority_queue使用std::less，这会创建一个最大堆，其中最大元素首先被移除。如果你想要创建一个最小堆，你可以传递std::greater作为Compare类型参数。

例如，如果你的Point类有一个x坐标和一个y坐标，你可能想根据x值或者y值的大小来比较Point对象。你可以定义一个比较类，如下所示：

struct Compare {
    bool operator()(const Point& p1, const Point& p2) {
        // 假设我们根据x坐标来比较两个点
        return p1.x > p2.x;
    }
};

使用这个Compare类，priority_queue会根据Point对象的x坐标进行排序，x值最大的点将会是队列中的第一个元素（如果你希望队列为最小堆，则应该将比较运算符改为<）。

在模板编程中，提供这种灵活性是非常有用的，因为这允许程序员自定义数据结构的行为以满足特定需求。

二、C++合并K个有序链表

C++合并K个有序链表，要求合并后链表依然有序。

代码：

#include <iostream>
#include <vector>
#include <queue>

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};

struct compare {
    bool operator()(const ListNode* l1, const ListNode* l2) {
        return l1->val > l2->val;
    }
};

ListNode* mergeKLists(std::vector<ListNode*>& lists) {
    std::priority_queue<ListNode*, std::vector<ListNode*>, compare> pq;

    for (auto list : lists) {
        if (list) {
            pq.push(list);   // 这里push的是链表的头节点，而不是链表本身，因为链表本身是一个指针，都是较小的值
        }
    }

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

    while (!pq.empty()) {
        tail->next = pq.top();
        pq.pop();
        tail = tail->next;

        if (tail->next) {
            pq.push(tail->next);  // next值再push到链表，比较大小，再pop出来
        }
    }

    ListNode* merged = dummy->next;
    delete dummy;
    return merged;
}

// 辅助函数：创建链表
ListNode* createList(const std::vector<int>& vals) {
    ListNode* dummy = new ListNode(0);
    ListNode* current = dummy;

    for (int val : vals) {
        current->next = new ListNode(val);
        current = current->next;
    }

    ListNode* head = dummy->next;
    delete dummy;
    return head;
}

// 辅助函数：打印链表
void printList(ListNode* head) {
    while (head) {
        std::cout << head->val << " ";
        head = head->next;
    }
    
    std::cout << std::endl;
}

int main() {
    // 创建一些链表
    std::vector<ListNode*> lists;
    lists.push_back(createList({1, 4, 5}));
    lists.push_back(createList({1, 3, 4}));
    lists.push_back(createList({2, 6}));

    // 合并链表
    ListNode* mergedList = mergeKLists(lists);

    // 打印合并后的链表
    std::cout << "Merged List: ";
    printList(mergedList);

    // 清理内存
    while (mergedList != nullptr) {
        ListNode* temp = mergedList;
        mergedList = mergedList->next;
        delete temp;
    }

    return 0;
}

运行结果：
Merged List: 1 1 2 3 4 4 5 6

mergeKLists函数说明

mergeKLists这个函数的目的是将 k 个有序链表合并成一个有序链表。下面是逐步的解释：

1. 初始化优先队列（最小堆）：

   • std::priority_queue<ListNode*, std::vector<ListNode*>, compare> pq;
   • 这行代码创建了一个最小堆，用于存储链表的节点。这里使用了一个自定义的比较函数 compare，确保队列总是按照节点的值从小到大排列。

2. 将所有链表的头节点加入优先队列：

   • for (auto list : lists) { if (list) pq.push(list); }
   • 这个循环遍历每个链表，并将每个链表的头节点（如果存在）加入优先队列。这样，队列中始终保存着当前未合并链表中最小的几个节点。

3. 合并链表：

   • 创建一个虚拟头节点 ListNode* dummy = new ListNode(0); 和一个尾指针 ListNode* tail = dummy; 用于构建新的合并后的链表。
   • 然后进入一个循环，此循环会持续直到优先队列为空：
     • while (!pq.empty()) { ... }
     • 在循环内部，从优先队列中取出最小的节点（即队列顶部的节点）并将其加入到合并后的链表中。
     • tail->next = pq.top(); pq.pop();
     • 将 tail 指针移动到新加入的节点上。
     • tail = tail->next;
     • 如果新加入的节点有后续节点（即 tail->next 不为空），则将这个后续节点加入优先队列中，以便在后续的迭代中考虑。

4. 返回合并后的链表：

   • 最后，函数返回合并后链表的头节点，即 dummy->next。
   • ListNode* merged = dummy->next;
   • 在返回之前，删除虚拟头节点以避免内存泄漏。
   • delete dummy;

总之，这个函数通过使用优先队列来有效地找到每次应该添加到结果链表中的最小节点。
每次从队列中取出一个节点后，将其下一个节点（如果存在）加入队列，确保队列始终包含所有链表当前的最小节点。这样就可以按顺序合并所有链表。

如何获取合并后的头结点

在代码 ListNode* merged = dummy->next; 中，merged 是一个 ListNode 类型的指针，它被赋值为 dummy->next。这里的 dummy 是一个虚拟（哨兵）头节点，它不包含实际的数据，而是作为合并链表过程中的辅助节点。

让我们详细解释一下这个过程：

1. 虚拟头节点 (dummy) 的作用：

   • 在合并链表的过程中，为了方便处理边界情况（如空链表），通常会使用一个虚拟头节点。这个节点在开始时被创建，但它的值不被使用（在这个例子中，它被初始化为 0）。
   • 虚拟头节点的主要作用是提供一个统一的起始点，无论是否有实际的数据节点。这样可以简化代码，避免处理特殊情况。

2. 构建合并后的链表：

   • 在函数中，新的合并后的链表是通过不断地将节点添加到 dummy 节点之后构建的。这是通过移动 tail 指针来完成的，它始终指向当前合并链表的最后一个节点。

3. 设置 merged 指针：

   • 当所有的链表都被合并后，dummy 的下一个节点 (dummy->next) 实际上是合并后链表的第一个真实数据节点。
   • 通过 ListNode* merged = dummy->next;，我们将 merged 指针设置为指向这个第一个真实数据节点。
   • 这样，merged 就成为了合并后链表的头节点，而 dummy 节点已经完成了它的任务。

4. 返回合并后的链表：

   • 函数最终返回 merged，即指向合并后链表的头节点的指针。

5. 删除虚拟头节点：

   • 在返回 merged 之前，代码中删除了 dummy 节点（delete dummy;），这是为了避免内存泄漏。由于 merged 已经指向了合并后链表的实际起始位置，dummy 节点就不再需要了。

总结来说，ListNode* merged = dummy->next; 这行代码的目的是将 merged 指针设置为指向合并后链表的实际起始节点，从而可以返回正确的链表头部，同时避免包含不必要的虚拟头节点。