Python solution with detailed explanation


  • 0
    G

    Solution

    Merge k Sorted Lists https://leetcode.com/problems/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
            return
        
        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.next, curr = lnode, lnode # Statement makes sure old values are assigned.
                self.add_to_heap(i, heap, lists)
            return result.next
    

Log in to reply
 

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