本文共 1271 字，大约阅读时间需要 4 分钟。

合并K个有序链表，并且作为一个有序链表的形式返回。分析并描述它的复杂度。

示例:

输入:[  1->4->5,  1->3->4,  2->6]输出: 1->1->2->3->4->4->5->6

思路：每两个链表一合并，每一次规模缩减为原来的一半，直到最后剩两个链表合并为一个链表。

复杂度分析： 第一次两两合并是进行了k/2次，每次处理2n个值。第二次两两合并是进行了k/4次，每次处理4n个值。。。。最后（设第x次）一次两两合并，进行了一次合并（k/(2^x)=1,求出x=logk），每次处理 n*k个值。

所以O(n)=nklogk，因为每个链表长度可能不一样，nk就是所有链表总长度，因此O(n)=Nlogk（N为k个链表总长度）

class Solution {public:    ListNode* merge(ListNode* l1, ListNode* l2) {        ListNode *dummy=new ListNode (0), *p=dummy;        while(l1 && l2){            if(l1->val >= l2->val){                p->next=l2;                l2=l2->next;            }            else{                p->next=l1;                              l1=l1->next;            }            p=p->next;        }        if(l1) p->next=l1;        if(l2) p->next=l2;        return dummy->next;    }    ListNode* mergeKLists(vector
   
    & lists) {        if(lists.empty()) return nullptr;        while(lists.size()>1){            vector
    
     temp;            for(int i=1; i
     
      & lists) {        if(lists.empty()) return nullptr;        queue
      
       q{lists};        while(q.size()>1){            ListNode *a=q.front();            q.pop();            ListNode *b=q.front();            q.pop();            q.push(merge(a,b));        }        return q.front();    }};
      
     
    
   

转载地址：http://khabi.baihongyu.com/