Simple Python solution with min-heap


  • 0
    Y
    def merge_k_lists(lists):
        """Merge k sorted lists in O(n*log k) time.
    
        :param lists: a list of sorted linked lists
        :returns:     a sorted linked list which is the merged result
        """
        dummy = ListNode('dummy')
        min_heap = []
        # initialize the heap
        for head in lists:
            if head:
                heapq.heappush(min_heap, (head.val, head))
        last = dummy
        while min_heap:
            _, head = heapq.heappop(min_heap)
            last.next = head
            if head.next:
                heapq.heappush(min_heap, (head.next.val, head.next))
            last = last.next
        return dummy.next
    

Log in to reply
 

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