Created
September 15, 2015 11:42
-
-
Save junjiah/eb5daebea8aa740fe540 to your computer and use it in GitHub Desktop.
solved 'Merge k Sorted Lists' on LeetCode https://leetcode.com/problems/merge-k-sorted-lists/
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Definition for singly-linked list. | |
* struct ListNode { | |
* int val; | |
* ListNode *next; | |
* ListNode(int x) : val(x), next(NULL) {} | |
* }; | |
*/ | |
// Divide and conquer. | |
// From https://leetcode.com/discuss/9279/a-java-solution-based-on-priority-queue?show=10537#a10537 | |
class Solution { | |
public: | |
ListNode* mergeKLists(vector<ListNode*>& lists) { | |
lists_ptr_ = &lists; | |
return mergeKLists(0, lists.size()); | |
} | |
private: | |
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) { | |
ListNode pseudo_head(-1); | |
ListNode *to_append = &pseudo_head; | |
while (l1 && l2) { | |
if (l1->val < l2->val) { | |
to_append->next = l1; | |
l1 = l1->next; | |
} else { | |
to_append->next = l2; | |
l2 = l2->next; | |
} | |
to_append = to_append->next; | |
} | |
to_append->next = l1 ? l1 : l2; | |
return pseudo_head.next; | |
} | |
ListNode* mergeKLists(int start, int end) { | |
int sz = end - start; | |
switch (sz) { | |
case 0: | |
return NULL; | |
case 1: | |
return lists_ptr_->at(start); | |
case 2: | |
return mergeTwoLists(lists_ptr_->at(start), lists_ptr_->at(start + 1)); | |
default: | |
return mergeTwoLists( | |
mergeKLists(start, start + sz / 2), mergeKLists(start + sz / 2, end)); | |
} | |
} | |
vector<ListNode*> *lists_ptr_; | |
}; |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Definition for singly-linked list. | |
# class ListNode(object): | |
# def __init__(self, x): | |
# self.val = x | |
# self.next = None | |
# Use heap. | |
class Solution(object): | |
def mergeKLists(self, lists): | |
""" | |
:type lists: List[ListNode] | |
:rtype: ListNode | |
""" | |
heap = [(ls.val, ls) for ls in lists if ls] | |
heapq.heapify(heap) | |
to_append = pseudo_head = ListNode(-1) | |
replacetop, pop = heapq.heapreplace, heapq.heappop | |
while heap: | |
val, ls = heap[0] | |
if ls.next: | |
replacetop(heap, (ls.next.val, ls.next)) | |
else: | |
pop(heap) | |
to_append.next = ls | |
to_append = to_append.next | |
return pseudo_head.next | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment