Python Divide Conquer & k Heap

  • 0

    Divide Conquer

    Just use merge sort's idea to divide k lists and merge each two lists recursively. Time complexity is O(nlogk) assuming n is the total number of nodes.

    def mergeKLists(self, lists):
        def merge(l1, l2):
            p = head = ListNode(0) # dummy node
            while l1 or l2:
                if l1 and l2:
                    if l1.val <= l2.val:
               = l1
                        l1 =
               = l2
                        l2 =
                    p =
                elif l1 is None:
           = l2
                elif l2 is None:
           = l1
        def divide(lists, start, end):
            if start == end:
                return lists[start]
            mid = start + (end - start) / 2
            l1 = divide(lists, start, mid)
            l2 = divide(lists, mid + 1, end)
            return merge(l1, l2)
        return divide(lists, 0, len(lists) - 1) if lists else []

    K heap

    Use a heap of size k to pop the smallest element from each list and push the next element into the heap util every element is in and out from the heap.

    def mergeKLists(self, lists):
        :type lists: List[ListNode]
        :rtype: ListNode
        import heapq
        p = dummy = ListNode(-1)
        h = []
        for i in range(len(lists)):
            if lists[i] > 0:
                heapq.heappush(h, (lists[i].val, lists[i]))
        while h:
            curr = heapq.heappop(h)
            currlist = curr[1]
   = currlist
            p =
                heapq.heappush(h, (,

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.