Heap based Python solution

  • 0
    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
                    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


    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


    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

    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.