方法一：分治法（相当于对暴力法的优化）
class Solution {
private:ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {ListNode* dummyhead = new ListNode(0);ListNode* cur = dummyhead;while (list1 && list2) {if (list1->val < list2->val) {cur->next = list1;list1 = list1->next;} else {cur->next = list2;list2 = list2->next;}cur = cur->next;}cur->next = list1 ? list1 : list2;return dummyhead->next;}ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j) {int m = j - i;// 计算当前范围 [i, j) 之间的链表数量if (m == 0) {return nullptr; // 注意输入的 lists 可能是空的}if (m == 1) {return lists[i]; // 无需合并，直接返回}ListNode* left = mergeKLists(lists, i, i + m / 2);ListNode* right = mergeKLists(lists, i + m / 2, j);return mergeTwoLists(left, right);}public:ListNode* mergeKLists(vector<ListNode*>& lists) {return mergeKLists(lists, 0, lists.size());}
};输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
mergeKLists(0, 3)
├── mergeKLists(0, 1) → 返回 lists[0] (1 -> 4 -> 5)
└── mergeKLists(1, 3)
├── mergeKLists(1, 2) → 返回 lists[1] (1 -> 3 -> 4)
├── mergeKLists(2, 3) → 返回 lists[2] (2 -> 6)
└── mergeTwoLists(lists[1], lists[2]) → (1 -> 2 -> 3 -> 4 -> 6)
└── mergeTwoLists(lists[0], merge(lists[1], lists[2])) → (1 -> 1-> 2 -> 3 -> 4 -> 4-> 5 -> 6)
方法二：最小堆 / 优先级队列 priority_queue
class Solution {
public:ListNode* mergeKLists(vector<ListNode*>& lists) {auto cmp = [](const ListNode* a, const ListNode* b) {return a->val > b->val;};priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq;for (auto head : lists) {if (head) {pq.push(head);}}ListNode* dummyhead = new ListNode(0);ListNode* cur = dummyhead;while (!pq.empty()) {ListNode* node = pq.top();pq.pop();if (node->next) {pq.push(node->next);}cur->next = node;cur = cur->next;}ListNode* newhead = dummyhead->next;delete dummyhead;return newhead;}
};这里使用 Lambda 表达式，Lambda 表达式把函数看作对象。Lambda 表达式可以像对象一样使用，比如可以将它们赋给变量和作为参数传递，还可以像函数一样对其求值。Lambda 表达式本质上与函数声明非常类似。Lambda 表达式具体形式如下:
[capture](parameters)->return-type{
body
};
[捕获列表](参数列表) -> 返回类型 {
// 函数体
};
其中：
-
[捕获列表]：捕获外部变量的方式（[]表示不捕获任何变量，[=]表示按值捕获，[&]表示按引用捕获）。 -
(参数列表)：定义传递给 Lambda 的参数（类似普通函数的参数）。 -
-> 返回类型（可选）：指定返回值类型（可以省略，由编译器推导）。 -
{ 函数体 }：函数的具体实现。
这道题目中：
（1）定义 Lambda
[](ListNode* a, ListNode* b) { return a->val > b->val; }
（2）decltype(cmp) 用于自动推导 cmp 的类型，因为lambda没有名字。这样 priority_queue 就能正确使用 cmp进行排序。
（3）初始化 priority_queue，
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
-
ListNode*是存储的数据类型。 -
vector<ListNode*>是底层实现（默认vector）。 -
decltype(cmp)指定比较器的类型，pq(cmp)传入cmp作为构造函数参数。
当然也可以使用operator() 仿函数，对 () 进行重载
struct compare {bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; }};priority_queue<ListNode*, vector<ListNode*>, compare> pq;class Solution {
public:struct cmp {bool operator()(ListNode* a, ListNode* b) { return a->val > b->val; }};ListNode* mergeKLists(vector<ListNode*>& lists) {priority_queue<ListNode*, vector<ListNode*>, cmp> pq;for (auto head : lists) {if (head) {pq.push(head);}}ListNode* dummyhead = new ListNode(0);ListNode* cur = dummyhead;while (!pq.empty()) {ListNode* node = pq.top();pq.pop();if (node->next) {pq.push(node->next);}cur->next = node;cur = cur->next;}ListNode* newhead = dummyhead->next;delete dummyhead;return newhead;}
};operator() vs 普通函数
你可能会问：为什么不用普通函数，而要用 operator() ？
(1)普通函数:
bool myCompare(ListNode* a, ListNode* b) {return a->val > b->val;
}priority_queue<ListNode*, vector<ListNode*>, decltype(&myCompare)> pq(myCompare);
也可以，但 myCompare 需要用 &myCompare 传递，略显繁琐。使用 &myCompare，表示传递的是函数指针。
(2)使用 operator()（仿函数）:
struct compare {bool operator()(ListNode* a, ListNode* b) {return a->val > b->val;}
};
priority_queue<ListNode*, vector<ListNode*>, compare> pq;
更简洁，priority_queue 直接使用 compare 作为类型。
(3)使用 lambda（C++11）:
auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
priority_queue<ListNode*, vector<ListNode*>, decltype(cmp)> pq(cmp);
最简洁，省去 struct compare 定义，适用于单次使用。
