LeetCode hard也就这么回事

给你一个链表数组，每个链表都已经按升序排列。

请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 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

        老样子，先贴我的图，可以说是又快又好，不过这里原题给的是子链表有序（常规写法也能写，不难），如果子链表无序，那各位读者应该是焦头烂额+汗流浃背了

            这个题，其实看完我上一篇分享可以立马写出来了，链表排序？看完你也能手撕 
思路还是一样，先转换成数组存放，再排序，再存回链表中（思路很简单）
 

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<int> s;  // 存储所有链表节点的值的容器

        // 遍历所有链表，将节点的值依次放入容器中
        for (int i = 0; i < lists.size(); i++) {
            ListNode* cur = lists[i]; // 当前链表的头节点
            while (cur != nullptr) {
                s.push_back(cur->val); // 将节点值加入容器
                cur = cur->next; // 指针移动到下一个节点
            }
        }
        
        sort(s.begin(),s.end()); // 将容器中的值进行排序(升序)
        
        ListNode *tt = new ListNode(-1); // 创建一个哑节点 tt，用于构建结果链表
        ListNode *res = tt; // 使用 res 保存结果链表的头节点
        int i = 0; // 用于遍历排序后的容器 s
        
        // 遍历列表
        for (int j = 0; j < lists.size(); j++) {       
            ListNode* cur1 = lists[j]; // 当前链表的头节点
            while(cur1 != nullptr) {
                cur1->val = s[i++]; // 将排序后的值赋给当前节点
                tt->next = cur1; // 连接当前节点到结果链表
                tt = cur1; // tt 指针移动到当前节点
                cur1 = cur1->next; // cur1 指针移动到下一个节点
            }
        }
        
        return res->next; // 返回结果链表的头节点
    }
};

以下是LeetCode官方的各种题解，为大家添加上了注释

方法一：顺序合并

我们可以想到一种最朴素的方法：用一个变量 ans 来维护以及合并的链表，第 i次循环把第 i 个链表和 ans 合并，答案保存到 ans 中。

class Solution {
public:
    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode* a, ListNode* b) {
        // 如果其中一个链表为空，则直接返回另一个链表
        if ((!a) || (!b)) return a ? a : b;
        
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) {
                // 当a链表的值小于b链表的值时，将a链表的节点拼接到结果链表后面，并更新a链表的指针
                tail->next = aPtr; aPtr = aPtr->next;
            } else {
                // 当a链表的值大于等于b链表的值时，将b链表的节点拼接到结果链表后面，并更新b链表的指针
                tail->next = bPtr; bPtr = bPtr->next;
            }
            // 更新结果链表的尾指针
            tail = tail->next;
        }
        // 将剩下的未合并的链表直接拼接到结果链表的尾部
        tail->next = (aPtr ? aPtr : bPtr);
        
        // 返回结果链表
        return head.next;
    }

    // 合并K个有序链表
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode *ans = nullptr;
        for (size_t i = 0; i < lists.size(); ++i) {
            // 逐个合并链表，将结果保存到ans中
            ans = mergeTwoLists(ans, lists[i]);
        }
        // 返回最终的合并结果
        return ans;
    }
};

方法二：分治合并

考虑优化方法一，用分治的方法进行合并。

class Solution {
public:
    // 合并两个有序链表
    ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
        if ((!a) || (!b)) return a ? a : b; // 如果其中一个链表为空，则直接返回另一个链表
        ListNode head, *tail = &head, *aPtr = a, *bPtr = b;
        while (aPtr && bPtr) {
            if (aPtr->val < bPtr->val) { // 比较两个节点的值，将较小的节点接入结果链表
                tail->next = aPtr; 
                aPtr = aPtr->next; // 更新a链表指针
            } else {
                tail->next = bPtr; 
                bPtr = bPtr->next; // 更新b链表指针
            }
            tail = tail->next; // 更新结果链表的尾节点
        }
        tail->next = (aPtr ? aPtr : bPtr); // 将剩余未合并完成的节点接入结果链表
        return head.next; // 返回结果链表的头节点
    }

    // 递归合并多个有序链表
    ListNode* merge(vector <ListNode*> &lists, int l, int r) {
        if (l == r) return lists[l]; // 当l和r相等时，表示只有一个链表，直接返回该链表
        if (l > r) return nullptr; // 当l大于r时，表示没有待合并的链表，返回空指针
        int mid = (l + r) >> 1; // 计算中间位置
        return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r)); // 递归合并左右两个部分
    }

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1); // 调用递归函数，合并整个链表数组
    }
};

方法三：使用优先队列合并

这个方法和前两种方法的思路有所不同，我们需要维护当前每个链表没有被合并的元素的最前面一个，k 个链表就最多有 k 个满足这样条件的元素，每次在这些元素里面选取 val 属性最小的元素合并到答案中。在选取最小元素的时候，我们可以用优先队列来优化这个过程。
 

class Solution {
public:
    // 定义结构体Status，用于在优先队列中存储节点信息
    struct Status {
        int val; // 节点的值
        ListNode *ptr; // 节点指针
        bool operator < (const Status &rhs) const {
            return val > rhs.val; // 优先队列按照节点值的大小进行排序
        }
    };

    priority_queue<Status> q; // 创建优先队列q，按照节点值的大小进行排序

    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 将每个链表的第一个节点放入优先队列
        for (auto node : lists) {
            if (node)
                q.push({node->val, node});
        }

        ListNode head, *tail = &head; // 创建结果链表的头节点head和尾节点tail
        while (!q.empty()) {
            auto f = q.top();
            q.pop();
            tail->next = f.ptr; // 将当前队列中最小的节点连接到结果链表的尾部
            tail = tail->next; // 更新尾节点为当前节点

            if (f.ptr->next)
                q.push({f.ptr->next->val, f.ptr->next}); // 如果当前节点还有下一个节点，则将下一个节点放入优先队列继续排序
        }

        return head.next; // 返回结果链表的头节点
    }
};