题解 | #合并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
        // merge sort
        if (lists.empty()) return nullptr;
        return helper(lists,0,lists.size()-1);
    }

    ListNode* helper(vector<ListNode*>& lists, int l, int r){
        if (l==r) return lists[r];
        int mid = l + (r-l)/2;
        ListNode* left = helper(lists,l,mid);
        ListNode* right = helper(lists,mid+1,r);
        return merge(left,right);
    }

    ListNode* merge(ListNode* h1, ListNode* h2){
        ListNode* root = new ListNode(0), *cur = root;
        while(h1&&h2){
            if(h1->val<h2->val){
                cur->next = h1;
                h1 = h1->next;
            }else{
                cur->next = h2;
                h2 = h2->next;
            }
            cur = cur->next;
        }
        // process remaining nodes
        while(h1){
            cur->next = h1;
            h1 = h1->next;
            cur = cur->next;
        }
        while(h2){
            cur->next = h2;
            h2 = h2->next;
            cur = cur->next;
        }
        return root->next;
    }
};