[LitCode]104.k個の並べ替えチェーンを連結する

k個の並べ替えチェーンを結合し、結合後の並べ替えチェーンを返します.その複雑さを解析して説明しようとする.
サンプル:3つの並べ替えチェーン［2->>4->null,null,-1->nullを与え、戻ります. -1->2->>4->null

/**
 * Definition of ListNode
 * class ListNode {
 * public:
 *     int val;
 *     ListNode *next;
 *     ListNode(int val) {
 *         this->val = val;
 *         this->next = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param lists: a list of ListNode
     * @return: The head of one sorted list.
     */
    ListNode *mergeKLists(vector &lists) {
        return partition(lists, 0, lists.size() - 1);
    }
    ListNode* partition(vector& lists, int start, int end) {
        if(start == end) {
            return lists[start];
        }
        if(start < end) {
            int mid = (start + end) / 2;            
            ListNode* l1 = partition(lists, start, mid);
            ListNode* l2 = partition(lists, mid + 1, end);
            return mergeTwoLists(l1, l2);
        }       
        return NULL;
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1==NULL){ 
            return l2;  
        }else if(l2==NULL){  
            return l1;  
        }  
        ListNode *pMergeHead=NULL;  
        if(l1->valval){  
            pMergeHead=l1;  
            pMergeHead->next=mergeTwoLists(l1->next,l2);  
        }else{  
            pMergeHead=l2;  
            pMergeHead->next=mergeTwoLists(l1,l2->next);  
        }  
        return pMergeHead;  
    }
};

    ListNode *mergeKLists(vector &lists) {
         int length = lists.size();
        if (length == 0)
            return NULL;
        while (lists.size() >1)
        {
            ListNode* p1 = lists.front ();
            lists.erase(lists.begin());
            ListNode* p2 = lists.front();
            lists.erase(lists.begin());
            lists.push_back(mergeTwoLists(p1, p2));
        }
        return lists[0];    
    }
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        if(l1==NULL){ 
            return l2;  
        }else if(l2==NULL){  
            return l1;  
        }  
        ListNode *pMergeHead=NULL;  
        if(l1->valval){  
            pMergeHead=l1;  
            pMergeHead->next=mergeTwoLists(l1->next,l2);  
        }else{  
            pMergeHead=l2;  
            pMergeHead->next=mergeTwoLists(l1,l2->next);  
        }  
        return pMergeHead;  
    }