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

/**
 * struct ListNode {
 *	int val;
 *	struct ListNode *next;
 *	ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param lists ListNode类vector 
     * @return ListNode类
     */
     ListNode* megertwoLists(ListNode* node1, ListNode* node2)
    {
        // 两个排好序的链表
        if (!node1) return node2;
        if (!node2) return node1;
        ListNode* res = new ListNode(-1);
        ListNode* p = res;
        while (node1 && node2)
        {
            if (node1->val > node2->val)
                {res->next = node2;
                node2 = node2->next;}
            else
                {res->next = node1;
                node1 = node1->next;}
            res = res->next;
        }
        if (!node1) res->next = node2;
        if (!node2) res->next = node1;
        return p->next;
    }

    ListNode* divideMerge(vector<ListNode*>& lists, int left, int right)
    {   
        int mid;
        if (left > right)
            return  nullptr;
        else if (left == right)
            return lists[left];
        else
            {
                mid = (left+right) / 2;
                return megertwoLists(divideMerge(lists, left, mid), divideMerge(lists, mid+1, right));
            }
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        // write code here
        return divideMerge(lists, 0, lists.size()-1);
    }

    

};