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:
                        p.next = l1
                        l1 = l1.next
                    else:
                        p.next = l2
                        l2 = l2.next
                    p = p.next
                        
                elif l1 is None:
                    p.next = l2
                    break
                elif l2 is None:
                    p.next = l1
                    break        
            return head.next
                
        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]
            p.next = currlist
            p = p.next
            if currlist.next:
                heapq.heappush(h, (currlist.next.val, currlist.next))
        
        return dummy.next

Log in to reply
 

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