Python solution using min heap - O(n + logn) 422ms


  • 0
    G
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    class Solution:
        # @param {ListNode[]} lists
        # @return {ListNode}
        # 5:48
        def mergeKLists(self, lists):
            if not lists:
                return None
    
            dummyNode = cur = ListNode(0)
            minHeap = [(l.val, l) for l in lists if l]
            heapq.heapify(minHeap)
    
            while minHeap:
                cur.next = heapq.heappop(minHeap)[1]
                cur = cur.next
    
                if cur.next:
                    heapq.heappush(minHeap, (cur.next.val, cur.next))
    
            return dummyNode.next

Log in to reply
 

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