方法一：分治法（相当于对暴力法的优化）

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 定义，适用于单次使用。