Merge k Sorted Lists

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

解题思路：

1、分治方法，两两合并。设每个链表的长度为n，有k个链表，那么每次合并最多扫描所有的元素，共扫描k/2+k/4+...+1=k次，因此时间复杂度为O(nk*k)=O(nk^2)。代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        int len=lists.size();
        if(len==0){
            return NULL;
        }
        if(len==1){
            return lists[0];
        }
        vector tempLists;
        for(int i=0; ival>list2->val){
                rear->next=list2;
                list2=list2->next;
            }else{
                rear->next=list1;
                list1=list1->next;
            }
            rear=rear->next;
        }
        if(list1!=NULL){
            rear->next=list1;
        }
        if(list2!=NULL){
            rear->next=list2;
        }
        rear=head;
        head=head->next;
        delete rear;
        return head;
    }
};

2、可以用一个最小堆来存储每个链表的头结点，每次将最小元素出列，并维护最小堆。建堆的时间复杂度为O(k*lgk)，对于每个链表元素，执行shiftdown的时间复杂度最大为O(lgk)，共有nk个链表元素，因此算法的总时间复杂度为O(nlgk+nklgk)=O(nklgk)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* mergeKLists(vector& lists) {
        int len=lists.size();
        if(len==0){
            return NULL;
        }
        ListNode* head=new ListNode(0), *rear=head;
        
        ListNode* minHeap[len]; //用一个最小堆来记录
        int minHeadLength=0;  //最小堆的有效长度
        
        for(int i=0; i0){
            rear->next=minHeap[0];
            rear=rear->next;
            minHeap[0]=minHeap[0]->next;
            if(minHeap[0]==NULL){
                minHeap[0]=minHeap[minHeadLength-1];
                minHeadLength--;
            }
            shiftDown(minHeap, minHeadLength, 0);
        }
        
        rear=head;
        head=head->next;
        delete rear;
        return head;
    }
    
    void buildMinHeap(ListNode** minHeap, int len){
        for(int i=(len-2)/2; i>=0; i--){
            shiftDown(minHeap, len, i);
        }
    }
    
    void shiftDown(ListNode** minHeap, int len, int index){
        int target=2*index+1;
        if(target>=len){
            return;
        }
        if(target+1valval){
            target = target+1;
        }
        if(minHeap[index]->val>minHeap[target]->val){
            swap(minHeap, index, target);
            shiftDown(minHeap, len, target);
        }
    }
    
    void swap(ListNode** minHeap, int i, int j){
        ListNode* tempNode=minHeap[i];
        minHeap[i]=minHeap[j];
        minHeap[j]=tempNode;
    }
};

相关博文：

定制桌面成功案例

海量文档查同或聚类问题 -- Locality Sensitive Hash 算法 （转）

汉字转拼音c/c++源码，支持gb2312和utf8

数据库顶级会议——SIGMOD介绍