My python solution use heapq


  • 0
    W

    There was an old version of solution, but that version did some useless copy and return the answer in wrong format. This version of answer improve those shortcomings.

    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            if not lists:
                return []
                
            dummy = ListNode(0)
            
            heap = []
            step = dummy
            
            for i in range(len(lists)):
                if lists[i]:
                    heapq.heappush(heap,(lists[i].val, i))
            
            while heap:
                val, index = heapq.heappop(heap)
                step.next = lists[index]
                lists[index] = lists[index].next
                step = step.next
                if lists[index]:
                    heapq.heappush(heap,(lists[index].val, index))
                    
            step.next = None
            return dummy.next

Log in to reply
 

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