Q:Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

A: 像mergesort一样，两两merge。

递归版本：

ListNode *merge(ListNode *list1,ListNode *list2)    {        if(!list1)            return list2;        if(!list2)            return list1;        ListNode *head;        if(list1->val<=list2->val)        {            head = list1;            head->next = merge(list1->next,list2);        }else        {            head = list2;            head->next = merge(list1,list2->next);        }        return head;    }    ListNode *mergeKLists(vector
     
       &lists) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        ListNode *head = NULL;        for(int i=0;i
     

　　

 迭代版本：

ListNode *merge(ListNode *list1,ListNode *list2)    {        if(!list1)            return list2;        if(!list2)            return list1;        ListNode *head = NULL,*it1,*it2,*prev,*cur;        it1 = list1;        it2 = list2;        while(it1&&it2)        {            if(it1->val<=it2->val)            {                cur = it1;                it1 = it1->next;            }else{                cur = it2;                it2 = it2->next;            }            if(!head)            {                head = prev = cur;             }else            {                prev->next = cur;                prev = cur;            }        }                if(it1)            prev->next = it1;                if(it2)            prev->next = it2;                    return head;    }    ListNode *mergeKLists(vector
     
       &lists) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        ListNode *head = NULL;        for(int i=0;i