在python3中使用heapq模块合并k个排序列表

Question

问题：-合并k个排序列表

我想用min-heap解决这个问题，它可以用python中的heapq模块实现。 下面是函数的示例代码

heapq.heappush(listwithoutNone,(node.val, node))
        

但问题是python解释器引发了一个错误：

TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' heapq.heappush(listwithoutNone,(node.val, node))

因此，我想使用node.val作为minheap节点元素，因为我要传递一个元组，所以我应该在代码中做什么更改，以便minheap将堆与node.val进行heapify

提前谢谢

Answer 1

我想你说的是：Leetcode合并k个排序列表

我正在为您分享一个可行的解决方案：

head = curr = ListNode(0)    # Creating a dummy node
    lst = []
    for l in lists:
        if l:
 # Here we need to first push val so that heap can know which is minimum and which is maximum. 
 # If we insert directly node then heap can't work proper way (in this case heapq.heappop doesn't return minimum node).    
            lst.append((l.val,l))    

    
    heapq.heapify(lst)
    while lst:
        val,node = heapq.heappop(lst)
        curr.next = node
        curr = curr.next
        node = node.next
        if node:
            heapq.heappush(lst,(node.val,node))
    return head.next