Python straightforward NKlogK using PriorityQueue + Hashmap


  • 0
        def mergeKLists(self, lists):
    
            import heapq
            if not lists: return
            buffr = itr = ListNode(None)
            N, H = collections.defaultdict(list), []
            for h in lists: # building heap
                if h:
                    H.append(h.val)
                    N[h.val].append(h) # add to value -> node hashmap
            if not H: return 
            heapq.heapify(H)
            while H: 
                mn = heapq.heappop(H)
                itr.next = itr = N[mn].pop() # get node corresponding to value
                if itr.next: 
                    heapq.heappush(H, itr.next.val)
                    N[itr.next.val].append(itr.next)
            return buffr.next
    

Log in to reply
 

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