LeetCode #23 2018-07-30

23. Merge k Sorted Lists

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

Example:
Input:
[
   1->4->5,
   1->3->4,
   2->6
]
Output: 1->1->2->3->4->4->5->6

https://leetcode.com/problems/merge-k-sorted-lists/description/

这道题在分布式系统中非常常见，来自不同client的sorted list要在central server上面merge起来。这道题一般有三种做法，下面一一介绍并分析复杂度。
第一种做法思想最简单，把所有节点值放入一个临时list，然后对list进行排序，即可得到最终的结果。但此方法的时间复杂度和空间复杂度也是最高的。假设总共有k个list，每个list的最大长度是n，这时时间复杂度为O(nklognk), 空间复杂度为O(nk).
代码如下：

    # Solution1 - build-in sort
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        ret = []
        for lst in lists:
            while lst:
                ret.append(lst.val)
                lst = lst.next
        ret.sort()
        dummy = pre = ListNode(0)
        for num in ret:
            cur_node = ListNode(num)
            pre.next = cur_node
            pre = pre.next
        return dummy.next

第二种，有点类似于MergeSort的思路，就是分治法。思路是先分成两个子任务，然后递归求子任务，最后回溯回来。这道题也是这样，先把k个list分成两半，然后继续划分，直到剩下两个list就合并起来，合并时会用到Merge Two Sorted Lists这道题。我们来分析一下上述算法的时间复杂度。同样假设总共有k个list，每个list的最大长度是n，那么运行时间满足递推式T(k) = 2T(k/2)+O(nk)。根据主定理，可以算出算法的总时间复杂度是O(nklogk)。如果不了解主定理的朋友，可以参见[主定理-维基百科]。空间复杂度的话是递归栈的大小O(logk)。
代码如下：

    # Solution2 - devide & conquer
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        if not lists:
            return None
        if len(lists) == 1:
            return lists[0]
        mid = len(lists) / 2
        head1 = self.mergeKLists(lists[:mid])
        head2 = self.mergeKLists(lists[mid:])
        return self.mergeTwoLists(head1, head2)

    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        dummy = ListNode(0)
        dummy.next = l1
        pre = dummy
        while(l1 and l2):
            if l1.val <= l2.val:
                l1 = l1.next
            else:
                next = l2.next
                l2.next = pre.next
                pre.next = l2
                l2 = next
            pre = pre.next
        if l2:
            pre.next = l2
        return dummy.next

第三种，用到了堆的数据结构，思路比较难想到，但是其实原理比较简单。维护一个大小为k的堆，每次取堆顶的最小元素放到结果中，然后读取该元素的下一个元素放入堆中，重新维护好。因为每个链表是有序的，每次又是取当前k个元素中最小的，所以当所有链表都读完时结束，这个时候所有元素按从小到大放在结果链表中。这个算法每个元素要读取一次，即是nk次，然后每次读取元素要把新元素插入堆中要logk的复杂度，所以总时间复杂度是O(nklogk)。空间复杂度是堆的大小，即为O(k)。
代码如下：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    # Solution3 - heapq
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        from heapq import heappush, heappop, heapreplace, heapify
        dummy = pre = ListNode(0)
        count = 0
        heap = []
        for node in lists:
            if node:
                heapq.heappush(heap, (node.val, count, node))
            count += 1
        while heap:
            value, temp, node = heap[0]
            if node.next:
                heapreplace(heap, (node.next.val, count, node.next))
                count += 1
            else:
                heappop(heap)
            pre.next = node
            pre = node
        return dummy.next

感悟:
在加入heap之前，可以先判断一下node是否为空，为空代表对应链表已经把所有结点都加入结果链表了，就不用再加入heap中去了。