Merge k Sorted Lists

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)