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

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) {
        sort(lists.begin(),lists.end(),[](const ListNode * A,const ListNode *B){
            if(A && B)return A->val<B->val;
            else if(!A) return true;
            else if(!B) return false;
            else return false;});
        ListNode* ahead = new ListNode(0);
        ListNode* head = new ListNode(0);
        int len = lists.size();
        if(len == 0) return nullptr;
        int j ;
        for( j = 0; j < len; ++j){
            if(lists[j]){
                head = lists[j];
                break;
            }
        }
        ++j;
        ahead = head;
        for(int i = j; i < len; ++ i){
            ListNode* node = lists[i];
            if(!node) continue;
            ListNode* pre = nullptr;
            while(node){
                ListNode* nxt = node->next;
                while(head && head->val <= node->val){
                    pre = head;
                    head = head->next;
                }
                pre->next = node;
                node->next = head;
                pre = pre->next;
                head = pre->next;
                node = nxt;
            }
            head = ahead;
        }
        return ahead;
    }
};