Merge k Sorted Lists

Question

Merge k sorted linked lists and return it as one sorted list.

Analyze and describe its complexity.

Thoughts

方法1, 利用merge 2 sorted list

首先可以用merge 2 sorted list的方法，两两mergesort, 不过这种方法会超时

方法2

在方法1中，每个list被merge后在之后的loop中还要被遍历，一共遍历k-i遍 可以使用二分法, 在左右分别选择两个list来merge,这样可以将每个list被遍历的数量变为logk

Solution

方法1

def mergeKLists(self, lists):
    # write your code here
    if not lists:
        return None
    head = lists[0]
    for i in range(1, len(lists)):
        head = merge2Lists(head, lists[i])
    return head

方法2

"""
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:
            return None

        return self.mergeHelper(lists, 0, len(lists) - 1)


    def mergeHelper(self, lists, start, end):
        if start == end:
            return lists[start]
        mid = start + (end-start) / 2
        leftList = self.mergeHelper(lists, start, mid)
        rightList = self.mergeHelper(lists, mid + 1, end)

        return self.mergeTwoLists(leftList, rightList)

    def mergeTwoLists(self, l1, l2):
        # write your code here
        dummy = ListNode(0)
        lastNode = dummy
        while l1 and l2:
            if l1.val < l2.val:
                lastNode.next = l1
                l1 = l1.next
            else:
                lastNode.next = l2
                l2 = l2.next
            lastNode = lastNode.next
        if l1:
            lastNode.next = l1
        if l2:
            lastNode.next = l2
        return dummy.next