Heap based Python solution


  • 0
    B
    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            from heapq import heappush, heappop
    
            # might need to use heap, start with k heads of lists
            # using a heap , find the minimum of the list heads, 
            #add it to list advance by next node
    
            if lists is None or len(lists) == 0:
                return None
            
            nlen = len(lists)
            if nlen == 1:
                return lists[0]
            
            
            # { l1, l2 , ... lk}
            heap = []
            for x in xrange(nlen):
                lnode = lists[x]
                if lnode is not None:
                    heappush(heap, (lnode.val, lnode.next))
            
            result = None
            temp = None
            prev = None
            
            while len(heap) != 0:
                
                (val, node) = heappop(heap)
                if result is None:
                    result = ListNode(val)
                    result.next = None
                    prev = result
                else:
                    temp = ListNode(val)
                    prev.next = temp
                    prev = temp
                
                if temp is not None:
                    temp = temp.next
                
                if node is not None:
                    heappush(heap, (node.val, node.next))
                
    
            
            return result
    

  • 0
    Z

    Hi,

    Thanks for your posting, I have a question, why do you need to move temp to next, such as,
    if temp is not None:
    temp = temp.next

    I cannot find out this makes any sense.
    Thank you very much


  • 0
    D

    @zhang57

    For the following iteration of the while loop, we will probably run the "else:" case.
    Which means we're setting the temp node.
    Since this temp node was the temp.next from last iteration, we're esentially setting the next node in the list.
    Otherwise, we'd constantly be overwriting the temp node (and never setting its next pointer)


  • 0
    B

    Hi zhang57,

    Consider the very first scenario when result is None. At that instance, we initialize result with just the first popped node. In the second iteration , we initialize temp with popped value and we need to move to next in order to make it available for the next popped node (in the next iteration)


Log in to reply
 

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