1. heap
2. divide and conquer

3. bottom up merge

4. divide and conquer

"""
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 not lists or len(lists) == 0:
            return None

        lists = [list for list in lists if list != None]
        if len(lists) == 0:
            return None
        return self.divide_conquer(lists, 0, len(lists) - 1)



    def divide_conquer(self, lists, start, end):
        if start == end:
            return lists[start]

        mid = (start + end) // 2

        left = self.divide_conquer(lists, start, mid)
        right = self.divide_conquer(lists, mid + 1, end)

        return self.merge(left, right)


    def merge(self, left, right):

        dummy_node = ListNode(0)
        head = dummy_node

        while left != None and right != None:
            if left.val < right.val:
                head.next = left
                left = left.next
            else:
                head.next = right
                right = right.next

            head = head.next

        if left != None:
            head.next = left
        if right != None:
            head.next = right
        return dummy_node.next

1. bottom up merge

"""
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 not lists or len(lists) == 0:
            return None
        lists = [list for list in lists if list != None]
        if len(lists) == 0:
            return None


        while len(lists) > 1:
            new_list = []
            for i in range(0, len(lists), 2):
                if i + 1 < len(lists):
                    new_list.append(self.merge(lists[i], lists[i + 1]))
                else:
                    new_list.append(lists[i])
            lists = new_list
        return lists[0]


    def merge(self, left, right):
        dummy_node = ListNode(0)

        head = dummy_node

        while left != None and right != None:
            if left.val < right.val:
                head.next = left
                left = left.next
            else:
                head.next = right
                right = right.next
            head = head.next
        if left != None:
            head.next = left
        if right != None:
            head.next = right
        return dummy_node.next