[C++] LeetCode 23. 合并K个排序链表

题目

合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:

[

1->4->5,

1->3->4,

2->6

]

输出: 1->1->2->3->4->4->5->6

方法一

这题可以考虑用二路归并排序，也就是分治法，两两一组合并，最终得到有序的链表。

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *merge(ListNode *p1,ListNode *p2){
        ListNode dummy(-1),*root=&dummy;
        while(p1!=NULL&&p2!=NULL){
            if(p1->val<p2->val){
                root->next=p1;
                p1=p1->next;
            }
            else{
                root->next=p2;
                p2=p2->next;
            }
            root=root->next;
        }
        if(p1==NULL) root->next=p2;
        else root->next=p1;
        return dummy.next;
    }
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> tmp;
        int n=lists.size();
        while(n>1){
            int i=0,j=0;
            for(i=0,j=0;i<n-1;i+=2){
                ListNode* t=merge(lists[i],lists[i+1]);
                if(t!=NULL)
                    lists[j++]=t;
            }
            if(i==n-1) lists[j++]=lists[i];
            n=j;
        }
        return lists.empty()?NULL:lists[0];
    }
};
           

方法二

分治法需要多次

merge

的过程，每个链表既然已经有序了，其实每次只需用从

k

个链表的头结点中选出最小的即可，那么可以考虑把

k

个链表的头结点放入优先级队列中（优先级队列一般是大顶堆，这里要做一下处理，变成小顶堆），然后每次取出

top

即为最小，在

top

对应节点的下一个节点放入优先级队列中即可。优先级队列插入的时间复杂度是

o(logn)

，而取出

top

的时间复杂度是

o(1)

，所以可以较大的提高效率

代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class cmp{
public:
    bool operator()(const ListNode* p1,const ListNode* p2){
        return p1->val>p2->val;
    }     
};

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