题目

merge-k-sorted-lists

算法

* 直接模拟

• O(nklgk)
• 二分思想
• 把每个list和与他相邻的 链表结合，规模小一半，重复

* 最小堆

• k个链表的第一个元素放入最小堆，自动排序
• 每次取出最小元素
• 然后将取出元素的下一个元素加入堆中，下次仍是相同的操作

测试程序

//数组生成链表

ListNode* createList(int a[],int n){
    ListNode* head=NULL, *p=NULL;
    for(int i=0;i<n;i++){
        if(head==NULL)
            head=p=new ListNode(a[i]);
        else{
            p->next=new ListNode(a[i]);
            p=p->next;
        }
    }
    return head;
}


void printlist(ListNode* h){
    while(h!=NULL){
        printf("%d ",h->val);
        h=h->next;
    }
    printf("\n");
}

int main(){
    int a[]={1,2,3,5,6,7};
    ListNode* p1=createList(a,sizeof(a)/sizeof(int));
    printlist(p1);
    return 0;
}

代码

* 直接模拟

class Solution {
public:
    ListNode *mergeKLists(vector<ListNode *> &lists) {
        if (lists.size() == 0) return NULL;
        int n = lists.size();
        while (n > 1) {
            int k = (n + 1) / 2;
            for (int i = 0; i < n / 2; ++i) {
                lists[i] = mergeTwoLists(lists[i], lists[i + k]);
            }
            n = k;
        }
        return lists[0];
    }

    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode *head = new ListNode(-1);
        ListNode *cur = head;
        while (l1 && l2) {
            if (l1->val < l2->val) {
                cur->next = l1;
                l1 = l1->next;
            } else {
                cur->next = l2;
                l2 = l2->next;
            }
            cur = cur->next;
        }
        if (l1) cur->next = l1;
        if (l2) cur->next = l2;
        return head->next;
    }
};

* 最小堆

struct cmp{
    bool operator() (ListNode* a,ListNode* b){
        return a->val>b->val;
    }
};

class  Solution{
public:
    ListNode* mergeKLists(vector<ListNode* >&lists){
        priority_queue<ListNode*,vector<ListNode*>,cmp > q;
        for(int i=0;i<lists.size();++i){
            if(lists[i]) q.push(lists[i]);
        }
        ListNode* head=NULL,*pre=NULL,*tmp=NULL;
        while(!q.empty()){
            tmp=q.top();
            q.pop();
            if(!pre) head=tmp;
            else pre->next=tmp;
            pre=tmp;
            if(tmp->next) q.push(tmp->next);
        }
        return head;
    }

};