solution 1: 暴力莽

class Solution{
public:
    //Solution 1: 合并到, 同一个串,O(k*k*n), 设n为链表长度
    ListNode* merget2Lists(ListNode* l1, ListNode* l2){
        ListNode dummy(0);
        ListNode* tail = &dummy;
        dummy.next = l1;

        while(tail->next and l2){
            l1 = tail->next;
            if(l1->val >= l2->val){
                ListNode* newnode = new ListNode(l2->val);
                tail->next = newnode;
                newnode->next = l1;
                l2 = l2->next;
            }
            else tail = tail->next;
        }

        if(!tail->next) l1 = l2;
        else l1 = nullptr;
        while(l1){
            tail->next = new ListNode(l1->val);
            tail = tail->next;
            l1 = l1->next;
        }
        return dummy.next;
    }


    ListNode* mergeKLists(vector<ListNode*>& lists) {
        if(lists.size() == 0) return nullptr;
        else if(lists.size() == 1) return lists[0];

        ListNode dummy(0);   
        ListNode* tail = &dummy;
        int flag = 0;
        for(auto list = lists.begin(); list < lists.end();){
            tail->next = merget2Lists(tail->next, *list);
            list ++;
        }           
        return dummy.next;
    }
}

二分merge, 设每个节点深度为n, O(nklogk)

class Solution{
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        return merge(lists, 0, lists.size() - 1);
    }    
private:
    ListNode* merge(vector<ListNode*>&lists, int l, int r){
        if(l > r) return nullptr;
        else if(l == r) return lists[l];

        int mid = (l + r) / 2;
        ListNode* l1 = merge(lists, l, mid);
        ListNode* l2 = merge(lists, mid + 1, r);

        // mergeTwoLists   
        return mergeTwoLists(l1, l2);
    }
    ListNode* mergeTwoLists(ListNode* left, ListNode* right){
        ListNode dummy(0);
        ListNode* tail = &dummy;
        while(left and right){
            if(left->val > right->val) swap(left, right); // 这里不错, 加少了很多判断
            tail->next = left;
            left = left->next;
            tail = tail->next;
        }
        if(left) tail->next = left;
        if(right) tail->next = right;
        return dummy.next;
    }
}

min heap, k个list, 假设每个list长n, 则时间复杂度O(nklogk)

class Solution{
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        ListNode dummy(0);
        ListNode* tail = &dummy;

        auto comp = [](ListNode* left, ListNode* right){return left->val > right->val;};
        priority_queue<ListNode*, vector<ListNode*>, decltype(comp)> q(comp);

        for(ListNode* list : lists){
            if(list) q.push(list);
        }

        while(!q.empty()){
            tail->next = q.top(), q.pop();
            tail = tail->next;
            if(tail->next) q.push(tail->next);
        }
        return dummy.next;
    }
}