康瑞部落

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<ListNode*>& lists) {
        int len=lists.size();
        if(len==0){
            return NULL;
        }
        if(len==1){
            return lists[0];
        }
        vector<ListNode*> tempLists;
        for(int i=0; i<len; i=i+2){
            if(i<len-1){
                tempLists.push_back(merge2Lists(lists[i], lists[i+1]));
            }else{
                tempLists.push_back(lists[i]);
            }
        }
        return mergeKLists(tempLists);
    }
    
    ListNode* merge2Lists(ListNode* list1, ListNode* list2){
        ListNode* head=new ListNode(0), *rear=head;
        while(list1!=NULL&&list2!=NULL){
            if(list1->val>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<ListNode*>& 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; i<len; i++){
            if(lists[i]!=NULL){
                minHeap[minHeadLength]=lists[i];
                minHeadLength++;
            }
        }
        
        buildMinHeap(minHeap, minHeadLength);
        
        while(minHeadLength>0){
            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+1<len&&minHeap[target+1]->val<minHeap[target]->val){
            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;
    }
};