合并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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/merge-k-sorted-lists
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解

这个问题可以使用分治法来解决。具体来说，我们可以将K个链表分成两个子问题，分别递归地解决左半部分和右半部分，然后将左半部分和右半部分的解合并起来。我们可以使用归并排序的思想来合并两个链表。

在代码中，mergeKLists函数是主函数，它首先判断链表数组是否为空或只有一个链表，如果是，则直接返回该链表或空指针；否则，调用merge函数来合并链表数组。merge函数是递归函数，它将链表数组分成左半部分和右半部分，分别递归地解决左半部分和右半部分，然后将左半部分和右半部

C++代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // 如果链表数组为空，则直接返回空指针
        if (lists.empty()) return nullptr;
        // 如果链表数组只有一个链表，则直接返回该链表
        if (lists.size() == 1) return lists[0];
        // 如果链表数组有多个链表，则使用分治法将其合并
        return merge(lists, 0, lists.size() - 1);
    }
    
    ListNode* merge(vector<ListNode*>& lists, int left, int right) {
        // 如果左右指针相等，则返回该链表
        if (left == right) return lists[left];
        // 计算中间指针
        int mid = left + (right - left) / 2;
        // 递归合并左半部分和右半部分
        ListNode* l1 = merge(lists, left, mid);
        ListNode* l2 = merge(lists, mid + 1, right);
        // 合并两个链表
        return mergeTwoLists(l1, l2);
    }
    
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        // 创建一个哨兵节点，方便操作
        ListNode* dummy = new ListNode(0);
        // 创建一个指针，指向哨兵节点
        ListNode* cur = dummy;
        // 遍历两个链表，将小的节点依次添加到新链表中
        while (l1 && l2) {
            if (l1->val <= l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        // 如果l1或l2还有剩余节点，则直接添加到新链表的末尾
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        // 返回新链表的头节点
        return dummy->next;
    }
};