Merge k Sorted Lists

Total Accepted: 61378 Total Submissions: 285515 Difficulty: Hard

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

方法一、将几个有序的链表连接起来，思路是把每个链表的头部放在一个最小堆中。

 1 #include <iostream>
 2 #include <algorithm>  //std::make_heap(),std::pop_heap(),std::push_heap,std::sort_heap()
 3 #include <vector>
 4 
 5 using std::vector;
 6 
 7 struct ListNode {
 8     int val;
 9     ListNode *next;
10     ListNode(int x) : val(x), next(NULL) {}
11 };
12 
13 class Solution {
14 public:
15     ListNode* mergeKLists(vector<ListNode*>& lists) {
16         if(lists.empty())  return nullptr;
17         int n = lists.size();
18         vector<ListNode*> minHeap;
19         minHeap.reserve(n);
20         for(int i=0;i<n;i++)
21             minHeap.push_back(lists[i]);
22         make_heap(minHeap.begin(),minHeap.end(),greater);  //construct the first min heap
23 
24         ListNode head = ListNode(-1);
25         ListNode *p= &head;
26         while(minHeap.front() != nullptr)
27         {
28             p->next = minHeap.front(); 
29             pop_heap(minHeap.begin(), minHeap.end(),greater);
30             minHeap.pop_back();
31             minHeap.push_back(p->next->next);
32             push_heap(minHeap.begin(),minHeap.end(),greater);
33             p=p->next;
34         }  
35         return head.next;  
36     }
37 private:
38     static bool greater(ListNode* l1,ListNode* l2){
39         if(l1 == nullptr)  return true;
40         else if(l2 == nullptr)  return false;
41         else return l1->val >= l2->val;
42     }  
43 };
44 
45 int main()
46 {
47     vector<ListNode*> lists;
48     ListNode* list1 = new ListNode(1);
49     list1->next = new ListNode(3);
50     list1->next->next = new ListNode(6);
51 
52     ListNode* list2 = new ListNode(2);
53     list2->next = new ListNode(4);
54     list2->next->next = new ListNode(5);
55 
56     ListNode* list3 = new ListNode(100);
57 
58     lists.push_back(list1);
59     lists.push_back(list2);
60     lists.push_back(list3);
61 
62     Solution s;
63     ListNode *head;
64     head = s.mergeKLists(lists);
65     while(head!= nullptr)
66     {
67         std::cout << head->val << "->";
68         head = head->next;
69     }
70     return 0;
71 }

方法二、归并（>80%）

 1 #include <iostream>
 2 #include <algorithm>  //std::make_heap(),std::pop_heap(),std::push_heap,std::sort_heap()
 3 #include <vector>
 4 
 5 using std::vector;
 6 
 7 struct ListNode {
 8     int val;
 9     ListNode *next;
10     ListNode(int x) : val(x), next(NULL) {}
11 };
12 
13 class Solution {
14 public:
15     ListNode* mergeKLists(vector<ListNode*>& lists) {
16         if(lists.size() == 0)
17             return nullptr;
18         if(lists.size() == 1){
19             return lists.at(0);
20         }
21             
22         int length = lists.size();
23         int mid = (length-1)/2;
24         vector<ListNode*> list1(lists.begin(),lists.begin()+mid+1);
25         vector<ListNode*> list2(lists.begin()+mid+1,lists.end());
26     
27         ListNode* l1=mergeKLists(list1);
28         ListNode* l2=mergeKLists(list2);
29 
30         return merge2Lists(l1,l2);
31     }
32 
33     ListNode* merge2Lists(ListNode* l1,ListNode* l2){
34         ListNode  head = ListNode(-1);
35         ListNode* p=&head;
36         while(l1 != nullptr && l2 !=nullptr){
37             if(l2->val<l1->val){
38                 p->next=l2;
39                 l2=l2->next;
40                 p = p->next;     
41             }else{
42                 p->next=l1;
43                 l1=l1->next;
44                 p= p->next;
45             }
46         }
47         if(l1!=nullptr){
48             p->next = l1;  
49         }
50         else{
51             p->next = l2;  
52         }  
53         return head.next;
54     }
55 
56 };
57 
58 int main()
59 {
60     vector<ListNode*> lists;
61     ListNode* list1 = new ListNode(1);
62     list1->next = new ListNode(3);
63     list1->next->next = new ListNode(6);
64 
65     ListNode* list2 = new ListNode(2);
66     list2->next = new ListNode(4);
67     list2->next->next = new ListNode(5);
68 
69     ListNode* list3 = new ListNode(100);
70 
71     lists.push_back(list1);
72     lists.push_back(list2);
73     lists.push_back(list3);
74 
75     Solution s;
76     ListNode* head = new ListNode(-1);
77    // head = s.merge2Lists(list1, list2);
78     head = s.mergeKLists(lists);
79 
80     while(head!= nullptr)
81     {
82        std::cout << head->val << "->";
83        head = head->next;
84     }
85     return 0;
86 }