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

算法主要思想有以下两点:

1. 任意两个链表的合并算法设计，这比较简单，主要考察的的后插法构造链表
2. 两两合并算法的设计

public:
    ListNode *mergeTwoLists(ListNode * L1, ListNode *L2){
        if(L1 == NULL){
            return L2;
        }
        else if(L2 == NULL){
            return L1;
        }
        ListNode *Dummy = (ListNode *)malloc(sizeof(ListNode));
        Dummy->next = NULL;
        ListNode *tail = Dummy;
        ListNode *head = Dummy;
        while(L1 != NULL && L2 != NULL){
            if(L1->val < L2->val){
                tail->next = L1;
                L1 = L1->next;
                tail = tail->next;
                tail->next =NULL;
            }
            else{
                tail->next = L2;
                L2 = L2->next;
                tail = tail->next;
                tail->next =NULL;
            }
        }
        if(L1 != NULL){
            L2 = L1;
        }
        tail->next = L2;
        head = Dummy->next;
        Dummy->next = NULL;
        delete Dummy;
        return head;
    }
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if(lists.empty()){
            ListNode * nov = NULL;
            return nov;
        }
        int size = lists.size();
        vector<ListNode *> listsCap;
        while(size/2){
            if(size % 2 == 0){
                for(int i = 0; i < size; i+=2){
                    listsCap.push_back(mergeTwoLists(lists[i], lists[i+1]));
                }
                lists.swap(listsCap);
                listsCap.clear();
            }
            else{
                for(int i = 0; i < size-1; i+=2){
                    listsCap.push_back(mergeTwoLists(lists[i], lists[i+1]));
                }
                listsCap.push_back(lists[size-1]);
                lists.swap(listsCap);
                listsCap.clear();
            }
            size = lists.size();
        }
        return lists[0];
    }
};