Straightforward Python solution with heap - beats 97.41%


  • 0
    T

    use node.val as the heap cmp key

    # Definition for singly-linked list.
    # class ListNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.next = None
    
    import heapq
    class Solution(object):
        def mergeKLists(self, lists):
            """
            :type lists: List[ListNode]
            :rtype: ListNode
            """
            root=ListNode(0)
            rroot=root
            heap=[]
            for head in lists:
                if not head:
                    continue
                heapq.heappush(heap,(head.val,head))
            while heap:
                nsnode=heapq.heappop(heap)[1]
                rroot.next=nsnode
                rroot=rroot.next
                nsnode=nsnode.next
                if nsnode:
                    heapq.heappush(heap,(nsnode.val,nsnode))
            rroot.next=None
            return root.next
    

Log in to reply
 

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