Merge k Sorted Lists

发表于 | 分类于

[Leetcode] Merge k Sorted Lists

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

解题思路：
使用分治算法。思路是先分成两个子任务，然后递归求子任务，最后回溯回来。这个题目也是这样，先把k个list分成两半，然后继续划分，直到剩下两个list就合并起来。这个算法的时间复杂度的计算：假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。根据主定理，可以算出算法的总复杂度是O(nklogk)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution(object):
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if lists == None or len(lists) == 0:
            return None
        return self.helper(lists, 0, len(lists)-1)

    def helper(self,lists, l, r):
        if l < r:
            m = (l+r)/2
            return self.merge(self.helper(lists,l,m),self.helper(lists,m+1,r))
        return lists[l]

    def merge(self,l1,l2):
        dump = ListNode(0)
        dump.next = l1
        temp = dump
        while(l1 != None and l2 != None):
            if l1.val < l2.val:
                l1= l1.next
            else:
                t = l2.next
                temp.next = l2
                l2.next = l1
                l2 = t
            temp = temp.next

        if l2 != None:
            temp.next = l2
        return dump.next

第二种思路是使用堆排序。维护一个大小为k的堆，每次取堆顶的最小元素放到结果中，然后读取该元素的下一个元素放入堆中，重新维护好。因为每个链表是有序的，每次又是去当前k个元素中最小的，所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。这个算法每个元素要读取一次，即是k*n次，然后每次读取元素要把新元素插入堆中要logk的复杂度，所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小，即为O(k)。

代码略