LeetCode 23. Merge k Sorted Lists

Merge  k  sorted linked lists and return it as one sorted list. Analyze and describe its complexity. 这道题如果有第21题 合并两个链表的基础就会比较容易，具体合并链表的时候有两种思路 （1）如果k个list依次连起来（l1先和l2连起来，结果再和l3连起来，依次），时间复杂度是 N*K*K 会超时，具体计算方法如下： 假设有K个长度为N的list (l1,l2,l3...lK)， 然后计算最差情况下的时间复杂度，  l1+l2 ---> l12 最坏情况的操作是2N次 l12+l3 ---> l123 最坏情况下的操作是3N次 依次类推：最坏情况下总共操作：2N+3N+4N+...+kN = (2+k)*(k-1)*N/2 也就是 N*K*K 的时间复杂度 （2）如果两两连起来，像归并排序那样处理，时间复杂度是N*K*logK 就不会超时； 假设有8个长度为N的list (l1,l2,...,l8)，然后计算最差情况下的时间复杂度： 两两一组合并分三个阶段，第一阶段是8个长度为N的链表合并， 操作次数是2N*4 第二阶段是4个长度为2N的链表合并，操作次数是4N*2 第三阶段是2个长度为4N的链表合并，操作次数是8N*1 所以总共操作次数是 N*8*3 可以猜测出一半的结论是K个长度为N的list的时间复杂度是 N*K*logK   程序如下： /** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public: ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { ListNode* head= new ListNode(0); ListNode* p=head;//head->next为返回的指针 while(1) { if(l1 && l2){ if(l1->val<l2->val){ p->next=l1; p=l1; l1=l1->next; } else{ p->next=l2; p=l2; l2=l2->next; } } else if(l1 && l2==NULL){ p->next=l1; break; } else if(l1==NULL && l2){ p->next=l2; break; } else{ break; } } return head->next; } ListNode* mergeKLists(vector<ListNode*>& lists) { if(lists.size()==0) return NULL; vector<ListNode*> old_lists;//合并前的lists vector<ListNode*> new_lists;//合并后的lists old_lists.clear();new_lists.clear(); for(int i=0;i<lists.size();i++) old_lists.push_back(lists[i]); while(1) { if(old_lists.size()==1) break;//合并成一条链表就输出 int cnt=0; for(int i=0;i<old_lists.size()/2;i++) { new_lists.push_back(mergeTwoLists(old_lists[cnt],old_lists[cnt+1])); cnt+=2; } if(cnt<old_lists.size())//如果链表数是奇数，则合并完前面的两两组合后，还要加入最后一个链表 new_lists.push_back(old_lists[cnt]); old_lists.clear(); for(int i=0;i<new_lists.size();i++) old_lists.push_back(new_lists[i]); new_lists.clear(); } return old_lists[0]; }};