题解 | #合并k个已排序的链表#

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
     //采用分治法
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        return merge(lists, 0, lists.size());
    }

    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2) {
        auto dummy = new ListNode(-1); // 用哨兵节点简化代码逻辑
        auto cur = dummy; // cur 指向新链表的末尾
        while (list1 && list2) {
            if (list1->val < list2->val) {
                cur->next = list1; // 把 list1 加到新链表中
                list1 = list1->next;
            } else { // 注：相等的情况加哪个节点都是可以的
                cur->next = list2; // 把 list2 加到新链表中
                list2 = list2->next;
            }
            cur = cur->next;
        }
        cur->next = list1 ? list1 : list2; // 拼接剩余链表
        return dummy->next;
    }

    // 合并从 lists[i] 到 lists[j-1] 的链表
    ListNode *merge(vector<ListNode *> &lists, int i, int j) {
        int m = j - i;
        if (m == 0) return nullptr; // 注意输入的 lists 可能是空的
        if (m == 1) return lists[i]; // 无需合并，直接返回
        auto left = merge(lists, i, i + m / 2); // 合并左半部分
        auto right = merge(lists, i + m / 2, j); // 合并右半部分
        return mergeTwoLists(left, right); // 最后把左半和右半合并
    }

};