题目

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;

    }

};