23. Merge K Sorted Lists 合并k个有序链表

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

Difficulty: Hard

合并k个排序列表.是前面21. Merge Two Sorted Lists 混合插入有序链表的升级版.

解法1

最先想到的就是利用21. Merge Two Sorted Lists 混合插入有序链表拿第一个链表与第二个合并,合并结果在于第三个比较.这样需要合并k-1次才能完成.

/**
 * 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 n = lists.size();
        if (n==0) return NULL;
        ListNode* res = lists[0];
        for (int i=1;i < n;i++){
            ListNode* node = lists[i];
            res = mergeTwoLists(res,node);
        }
        return res;
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1==NULL) return l2;
        if (l2==NULL) return l1;
        ListNode* head = NULL;
        if (l1->val<l2->val)
        {
            head = l1;
            head->next = mergeTwoLists(l1->next,l2);
        }
        else
        {
            head = l2;
            head->next = mergeTwoLists(l2->next,l1);
        }
        return head;
    }
};

解法2

这里需要用到分治法就是不停的对半划分,k个有序链表,先划分为两个k/2个链表合并的任务…. 举个例子k=6,先合并1和4,2和5,3和6 结果为3个链表,下一次再合并1和3,结果与2合并.这样做的好处我感觉就是便于理解大任务处理吧,效率上相比于解法1并没有提高,举个例子k=48,那么合并次数为24+12+6+3+1+1=47,与解法1一样.

/**
 * 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) {
        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[k+i]);
            n = k;
        }
        return lists[0];
    }
    ListNode* mergeTwoLists(ListNode* l1,ListNode* l2){
        if (l1==NULL) return l2;
        if (l2==NULL) return l1;
        ListNode* head = NULL;
        if (l1->val<l2->val)
        {
            head = l1;
            head->next = mergeTwoLists(l1->next,l2);
        }
        else
        {
            head = l2;
            head->next = mergeTwoLists(l2->next,l1);
        }
        return head;
    }  
};

解法3

这里用一个最小堆来解决,对里面存的是k个链表的第一个元素,那么堆顶元素就是最小的元素,取出来放到结果链表中,并把该元素的下一个元素放入最小堆中,最小队排序后又可以得到当前最小的元素.以此类推.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

bool cmp (ListNode* a, ListNode* b)
{
    if (a && b)
    {
        return a->val > b->val;
    }
    else if (!a) return false;
    else return true;
}

class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        vector<ListNode*> min;
        for (int i = 0; i < lists.size(); i++) {
            min.push_back(lists[i]);
            push_heap(min.begin(), min.end(), cmp);
        }
        
        ListNode* head = NULL,*pre = NULL,*top = NULL;
        while (!min.empty())
        {
            top = min[0];
            if (!top)
            {
                pop_heap(min.begin(), min.end(), cmp);
                min.pop_back();
                continue;
            }
            if (!head) head = top;
            if (pre) pre->next = top;
            pre = top;
            pop_heap(min.begin(),min.end(),cmp);
            min.pop_back();
            if (top->next)
            {
                min.push_back(top->next);
                push_heap(min.begin(), min.end(), cmp);
            }
        }
        return head;   
    }
};

利用priority_queue

priority_queue<Type,Container,Compare>    
    
//  Type 为数据类型     
//  Container 为保存数据的容器, 必须是用数组实现的容器,比如 vector, deque 但不能用list。STL里面默认用的是 vector    
//  Compare为元素比较方式。. 比较方式默认用 operator< , 所以如果你把后面俩个参数缺省的话,优先队列就是大顶堆,队头元素最大。    

关于priority_queue
1,关于STL中的priority_queue:确定用top()查看顶部元素时,该元素是具有最高优先级的一个元素. 调用pop()删除之后,将促使下一个元素进入该位置. 
2,如同stack和queue,priority_queue是一个基于基本序列容器进行构建的适配器,默认的序列器是vector.
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

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

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,*top = NULL;
        while (!q.empty()) {
            top = q.top();
            q.pop();
            if (!pre) head = top;
            else pre->next = top;
            pre = top;
            if (top->next) q.push(top->next);
        }
        return head; 
    }
};
 
comments powered by Disqus