Python solution with detailed explanation

  • 0


    Merge k Sorted Lists

    Use min heap of size k to merge: O(Nlog(k))

    • Maintain a min heap of size k and add the heads of each list to the heap.
    • Now pop the heap and add to result. Then add to heap the next node for the popped element.
    from heapq import heappush, heappop
    class Solution(object):
        def add_to_heap(self, i, heap, lists):
            if lists[i]:
                temp, lists[i].next = lists[i].next, None
                heappush(heap, (lists[i].val, (i, lists[i])))
                lists[i] = temp
        def mergeKLists(self, lists):
            :type lists: List[ListNode]
            :rtype: ListNode
            N, heap, result = len(lists), [], ListNode(-1)
            curr = result
            for i in range(N):
                self.add_to_heap(i, heap, lists)
            while len(heap):
                x, (i, lnode) = heappop(heap)
      , curr = lnode, lnode # Statement makes sure old values are assigned.
                self.add_to_heap(i, heap, lists)

Log in to reply

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