【LeetCode热题100】23. 合并 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$

四.解题思路

解法1：n个指针从n个链表的头开始同时移动，比较并插入最小值，而后指向最小值的指针后移。时间 $O(k^{2}n)$ 空间 $O(1)$
解法2：最小堆
维护当前每个链表没有被合并的元素的最前面一个，k个链表就最多有 k个满足这样条件的元素，每次在这些元素里面选取val属性最小的元素合并。在选取最小元素的时候，用最小堆存这k个满足条件的元素。
解法3：分治法两个两个比较

五.代码实现

解1

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode(-1);
        ListNode* sup = dummy;
        ListNode* tmp;
        int pMin = INT_MAX;
        vector<ListNode*>::iterator minIt = lists.begin();
        bool changed = true;
        while(changed)
        {   
            changed = false;
            for(vector<ListNode*>::iterator it = lists.begin(); it != lists.end();it++)
            {
                if(*it != nullptr && (*it)->val < pMin)
                {
                    changed = true;
                    minIt = it;
                    pMin = min((*it)->val, pMin);
                }    
            }
            if(changed)
            {
                tmp = *minIt;
                *minIt = (*minIt)->next;        
                sup->next = tmp;
                tmp = nullptr;
                sup = sup->next;
            }
            pMin = INT_MAX;
            tmp = nullptr;
        }
        return dummy->next;
    }
};

解2

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Compare {
public:
    bool operator()(const ListNode* l1, const ListNode* l2) const {
        return l1->val > l2->val;  
    }
};

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode* dummy = new ListNode(-1);
        ListNode* sup = dummy;
        priority_queue<ListNode*,vector<ListNode*>,Compare> listQueue;

        for(auto listnode :lists)
        {
            if(listnode) listQueue.push(listnode);
        }

        while(!listQueue.empty())
        {
            ListNode* t = listQueue.top();
            listQueue.pop();
            sup->next = t;
            sup = sup->next;
            if(t->next) listQueue.push(t->next);

        }
        return dummy->next;
    }
};

六.题目总结

在 C++ 标准模板库（STL）中，std::priority_queue 是一个容器适配器，它提供了对内部容器的有限访问，专门设计用来在固定集合中管理最大（或最小）的元素。priority_queue 通常实现为一个最大堆，其中最大的元素总是位于顶部。然而，它也可以配置为最小堆，这时最小的元素位于顶部。

std::priority_queue 的模板声明如下：

template<
    class T,
    class Container = std::vector<T>,
    class Compare = std::less<typename Container::value_type>
> class priority_queue;

这里有三个模板参数：

• T - 元素类型。
• Container - 实际用于存储数据的容器类型，必须是顺序容器，并支持 front(), push_back(),
  pop_back() 操作，比如 std::vector 或 std::deque。
• Compare - 一个用于元素比较的函数对象的类型。这个比较对象决定了元素的排序方式，从而影响优先队列中元素的优先级。

为什么需要一个类型而不是一个函数实例
当我们谈到模板参数时，特别是指 std::priority_queue 的第三个参数，我们指的是类型而不是特定的函数实例或函数指针。这是因为模板在编译时需要类型信息来生成代码，而不是运行时的函数实例。Compare 需要是一个类型，因为 STL 在编译时实例化容器和算法，而不是在运行时。

你提供的类型应该定义了 operator()，这使得其实例可以像函数一样被调用。因此，你通常会提供一个结构体或类，其中包含重载的 operator() 方法。priority_queue 使用这个类型的实例来比较元素，确定它们在堆中的顺序。

这种设计允许 priority_queue 具有更大的灵活性和泛化能力。通过模板参数化比较函数，可以在不改变容器代码的情况下，定制不同的排序行为。用户可以定义任何满足需求的比较逻辑，只要它遵循正确的接口（即提供 operator()）。

示例：使用自定义比较类型
想定义一个最小堆，你可以这样定义比较类型：

struct MinCompare {
    bool operator()(int lhs, int rhs) const {
        return lhs > rhs; // 对于最小堆，我们使用大于比较
    }
};

std::priority_queue<int, std::vector<int>, MinCompare> minHeap;

在这个例子中，MinCompare 是一个自定义的比较类型，它定义了 operator() 来实现最小堆的逻辑。priority_queue 使用 MinCompare 实例来比较元素并维持堆的结构。

通过将比较逻辑封装在类型中，priority_queue 能够在编译时获得所有必要的信息来正确地管理元素，同时为用户提供了定制其行为的灵活性。这就是为什么 priority_queue 需要一个比较类型而不是函数实例作为模板参数的原因。