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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution {
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;

        while (l1 && l2) {
            if (l1->val > l2->val) {
                cur->next = l2;
                l2 = l2->next;
            } else {
                cur->next = l1;
                l1 = l1->next;
            }
            cur = cur->next;
        }
        cur->next = l1 ? l1 : l2;
        return dummy->next;
    }

    ListNode* mergeKLists(vector<ListNode*>& lists, int i, int j) {
        int m = j - i;
        if (m == 0) return nullptr;
        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());
    }
};

分治