Merge K sorted List

题目描述

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

Example :

1 -> 10 -> 20
4 -> 11 -> 13
3 -> 8 -> 9

will result in

1 -> 3 -> 4 -> 8 -> 9 -> 10 -> 11 -> 13 -> 20

解题方法

利用heap的方法

维护一个size为k的heap

总时间复杂度是O(nklogk)。空间复杂度是堆的大小，即为O(k)

利用二分法

如果两两比较的话，worst case是第一个list很长，然后后面的List要不断地加到 后面，那个第一个list的每个元素都要visit n遍，时间复杂度就是O(n^2)

这种方法基本上是从头到尾遍历一遍，对于每个list来说是O(n),如果O(n)的复杂度 不能满足，那么就应该往O(logn)的方向想。

利用mergesort的思想，不断地将lists of list这个lists分成两半去合并。

那么运行时间满足递推式T(k) = 2T(k/2)+O(n*k)。 根据主定理，可以算出算法的总复杂度是O(nklogk)。 空间复杂度的话是递归栈的大小O(logk)。

Solution

heap的方法

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

class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        heap = []
        dummy = ListNode(0)
        length = len(A)
        current = dummy
        for head in A:
            heappush(heap, head.val)
        while heap:
            cur_min = heappop(heap)
            current.next = ListNode(cur_min)
            current = current.next
            for i in range(length):
                if A[i] and A[i].val == cur_min:
                    A[i] = A[i].next
                    if A[i]:
                        heappush(heap, A[i].val)
        return dummy.next

mergesort思想

class Solution:
    # @param A : list of linked list
    # @return the head node in the linked list
    def mergeKLists(self, A):
        if not A:
            return None
        length = len(A)
        return self.mergeHelper(A, 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)

    def mergeTwoLists(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        if not l1:
            return l2
        if not l2:
            return l1

        dummy = ListNode(0)
        head = dummy
        while l1 and l2:
            if l1.val < l2.val:
                head.next = l1
                head = head.next
                l1 = l1.next
            else:
                head.next = l2
                head = head.next
                l2 = l2.next

        # 注意这里是if，直接将后面的连上
        if l1:
            head.next = l1

        if l2:
            head.next = l2

        return dummy.next

Reference