Merge k sorted linked lists and return it as one sorted list.
Analyze and describe its complexity.
Example
Given lists:
[
2->4->null,
null,
-1->null
],
return -1->2->4->null.
Solution
Priority Queue: 类似枪梭子，多个枪梭子插在一个枪上，谁小，弹出谁。
PriorityQueue/Heap vs Divide Conquer
分治算法
Merge Sort 类似方法：
"""
Definition of ListNode
class ListNode(object):
def __init__(self, val, next=None):
self.val = val
self.next = next
"""
class Solution:
"""
@param lists: a list of ListNode
@return: The head of one sorted list.
"""
def mergeKLists(self, lists):
# write your code here
if lists == None or len(lists) == 0:
return None
return self.mergeKListsHelper(lists, 0, len(lists) - 1)
def merge(self, left, right):
dummy = ListNode(0)
tail = dummy
while left and right:
if left.val < right.val:
tail.next = left
tail = left
left = left.next
else:
tail.next = right
tail = right
right = right.next
if left:
tail.next = left
if right:
tail.next = right
return dummy.next
def mergeKListsHelper(self, lists, start, end):
if start == end:
return lists[start]
mid = (start + end) / 2
left = self.mergeKListsHelper(lists, start, mid)
right = self.mergeKListsHelper(lists, mid + 1, end)
return self.merge(left, right)