Merge k Sorted Lists

Date:

　　Nov, 7, 2017.

Problem:

　　https://leetcode.com/problems/merge-k-sorted-lists/discuss/

Description:

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

　　考虑暴力解法，写一个MergeTwoSortedLists对输入链表依次归并。

 1 class Solution:
 2     def mergeKLists(self, lists):
 3         if len(lists) == 0:
 4             return None
 5         while len(lists) > 1:
 6             lists.append(self.mergeTwoLists(lists[0], lists[1]))
 7             lists.pop(0)
 8             lists.pop(0)
 9         return lists[0]
10     def mergeTwoLists(self, list1, list2):
11         if list1 == None:
12             return list2
13         if list2 == None:
14             return list1
15         if list1.val <= list2.val:
16             list1.next = self.mergeTwoLists(list1.next, list2)
17             return list1
18         if list1.val > list2.val:
19             list2.next = self.mergeTwoLists(list1, list2.next)
20             return list2

　　提交，超过递归深度。

　　第一次见到这种错误类型……

　　那就写一个优先队列吧。

 1 class Solution {
 2 public:
 3     struct compare {
 4         bool operator()(const ListNode* l, const ListNode* r) {
 5             return l->val > r->val;
 6         }
 7     };
 8     ListNode *mergeKLists(vector<ListNode *> &lists) { 
 9         priority_queue<ListNode *, vector<ListNode *>, compare> q;
10         for (auto i : lists)
11             if (i)
12                 q.push(i);
13         if (q.empty())
14             return NULL;
15         ListNode* result = q.top();
16         q.pop();
17         if (result->next)
18             q.push(result->next);
19         ListNode* p = result;            
20         while (!q.empty()) {
21             p->next = q.top();
22             q.pop();
23             p = p->next;
24             if(p->next)
25                 q.push(p->next);
26         }
27         return result;
28     }
29 };

　　AC。时间复杂度为O(Nlog(N))。

　　mingjun的堆写法，效率与优先队列相似。

 1 static bool heapComp(ListNode* a, ListNode* b) {
 2         return a->val > b->val;
 3 }
 4 ListNode* mergeKLists(vector<ListNode*>& lists) { //make_heap
 5     ListNode head(0);
 6     ListNode *curNode = &head;
 7     vector<ListNode*> v;   
 8     for(int i =0; i<lists.size(); i++){
 9         if(lists[i]) v.push_back(lists[i]);
10     }
11     make_heap(v.begin(), v.end(), heapComp); //vector -> heap data strcture
12 
13     while(v.size()>0){
14         curNode->next=v.front();
15         pop_heap(v.begin(), v.end(), heapComp); 
16         v.pop_back(); 
17         curNode = curNode->next;
18         if(curNode->next) {
19             v.push_back(curNode->next); 
20             push_heap(v.begin(), v.end(), heapComp);
21         }
22     }
23     return head.next;
24 }