leetcode_merge_k_sorted_lists

发表于

难度：Hard

解题思路：
1.比较list[i]->val的大小，更新lists[i]＝list[i]->next。最后效率会比较低
2.按照merge2的思路，1+2->result,result+3->result,….以此类推。这个效率也不高

代码如下(思路2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/**
 * 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 nullptr;
        ListNode* result = lists[0];
        for(int i = 1; i < lists.size(); i++)
        {
            ListNode* l = lists[i];
            result = mergeTwoLists(result, l);
        }
        return result;
    }
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(-1);
        ListNode* cur = dummy;
        while(l1 != NULL && l2 != NULL)
        {
            if(l1->val < l2->val)
            {
                cur->next = l1;
                cur = cur->next;
                l1 = l1->next;
            }
            else
            {
                cur->next = l2;
                cur = cur->next;
                l2 = l2->next;
            }
        }
        if(l1 != NULL)
        {
            cur->next = l1;
        }
        if(l2 != NULL)
        {
            cur->next = l2;
        }
        return dummy->next;
    }
};

运行结果：316ms，超过7.19%

第三种思路：参考了“喜唰唰”的博客。这种算是第一种思路的优化方法，使用priority_queue。将lists中的每个节点放入priority_queue中，创建一个min_heap。之后每从queue中取出一个节点，则将该节点在其list中的下一个节点插入，以此类推直到全部节点都经过priority queue。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    struct compNode {
        bool operator()(ListNode *p, ListNode *q) const {
            return p->val>q->val;
        }  
    };

    ListNode *mergeKLists(vector<ListNode *> &lists) {
        priority_queue<ListNode*, vector<ListNode*>, compNode> pq;
        ListNode *dummy = new ListNode(0), *tail = dummy;
        
        for(int i=0; i<lists.size(); i++) 
            if(lists[i]) pq.push(lists[i]);
            
        while(!pq.empty()) {
            tail->next = pq.top();
            tail = tail->next;
            pq.pop();
            if(tail->next) pq.push(tail->next);
        }
        
        return dummy->next;
    }
};

运行时间：52ms，超过26.34%

ref:http://bangbingsyb.blogspot.com/2014/11/leetcode-merge-k-sorted-lists.html