Heapq for python AC code.


  • 0
    B
    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            
            if not lists:
                return []
                
            heap = []
            
            firstlists = []
            for i in range(len(lists)):
                firstlists.append(lists[i])
            
            for i in range(len(firstlists)):
                if firstlists[i]:
                    val = firstlists[i].val
                    firstlists[i] = firstlists[i].next
                    heapq.heappush(heap, (val, i))
                    
            result = []
            while heap:
                val, index = heapq.heappop(heap)
                result.append(val)
                if firstlists[index]:
                    val = firstlists[index].val
                    firstlists[index] = firstlists[index].next
                    heapq.heappush(heap, (val, index))
            
            return result

  • 0
    W

    Why do we need to copy the original list to the firstlists before we do merge?


Log in to reply
 

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