Merge K Sorted Lists

题目描述

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

解题方法

方法1

这一题最简单的方法就是利用merge 2 sorted lists的方法，不断地两两比较， 这样的 worst case是第一个list很长，后面的list很短但是都要加在后面，这样第一个List的每个元素都要 遍历 n 次（n为list的数量）， 那么时间复杂度就会为O(n^2)

方法2

上面一种最简单的方法时间复杂度太高，那么我们就应该想如何减少时间复杂度， 方法1基本上是从头到尾遍历一遍，对于每个list来说是O(n)的复杂度，如果O(n)的复杂度不能满足， 那我们就应该往O(logn)的方法想。

而O(logn)最经典的就是二分法了，如何对于这个lists，我们也采取二分法，这样对于每个 list它只需要跟LogN的的list来比较，这样必然降低了时间复杂度。

方法3 heap

方法2是在不能有extra space的时候的解法，如果可以有extra space, 因为它们已经都是sorted list, 所以可以建一个大小为n（n为list的数量）的heap, 将每个list的head也就是最小值放到Heap里， 然后不断地将heap的最小值加入Dummy node的后边，并且更新被加入的List的head。 就可以做到O(n)的复杂度。

Solution

主要的code, 省略了merge 2 sorted list的code

class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None

        length = len(lists)
        return self.mergeHelper(lists, 0, length - 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)

Reference