如何在python中将链表列表中的链表节点放置到堆中

Question

我认为标题比实际问题描述更令人困惑。这里是

我有一个链表的python列表，看起来有点像lists = [[1,4,5],[1,3,4],[2,6]]，并且链表节点被定义为

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

在我试图解决的问题中，第一步是将每个列表的第一个元素放入堆中。这是我的代码：

mylist1 = ListNode(1, ListNode(4, ListNode(5)))
mylist2 = ListNode(1, ListNode(3, ListNode(4)))
lists = [mylist1, mylist2]
import heapq
heap = []
for l in lists:
heapq.heappush(heap, (l.val, l))

当我运行此代码时，我得到以下异常：

Traceback (most recent call last):
File "<pyshell#29>", line 2, in <module>
heapq.heappush(heap, (l.val, l))
TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'

我想我理解那里发生了什么，python不是把l当作一个单独的节点，而是当作一个完整的列表。所以我的问题是，如何将每个列表中的第一个节点放到python中的堆中？我觉得答案很简单，但我遗漏了一些重要的东西。

编辑

我正在努力解决这个问题，https://leetcode.com/problems/merge-k-sorted-lists/.方法是使用堆，但我不想将所有元素都插入其中，我想做的是插入每个列表的第一个元素，找到最小元素，然后插入列表中最小的下一个元素，以此类推，直到我遍历所有元素。

Answer 1

将(l.val, l)放在堆上的问题是，当两个元组在第一个成员(val(中具有相同的值时，第二个成员值之间(即列表之间(将进行比较。但是这个操作没有定义。您可以通过在这些元组中的两个成员之间放置第三个唯一值来避免这种情况。所以你可以这样定义你的堆：

for i, l in enumerate(lists):
heapq.heappush(heap, (l.val, i, l))

由于列表可能为空，您应该添加一个条件：

for i, l in enumerate(lists):
if l:
heapq.heappush(heap, (l.val, i, l))

这也是告诉您，首先在标准列表中收集这些元组，然后在其上调用heapify会更高效：

heap = [(l.val, i, l) for i, l in enumerate(lists) if l]
heapq.heapify(heap);

这不是你的问题，但如果你不能使完整的逻辑工作，这里有一个代码剩余的剧透：

tail = dummy = ListNode() while heap: _, i, tail.next = heap[0] tail = tail.next if tail.next: heapq.heapreplace(heap, (tail.next.val, i, tail.next)) else: heapq.heappop(heap) return dummy.next

Answer 2

你在找这样的东西吗=>

class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
def __lt__(self,other):
return self.val < other.val
def __le__(self,other):
return self.val <= other.val

mylist1 = ListNode(1, ListNode(4, ListNode(5)))
mylist2 = ListNode(1, ListNode(3, ListNode(4)))
nodes = [mylist1,mylist2]
import heapq
heap = []
for l in nodes:
heapq.heappush(heap, (l.val,l))
print(heap)

也可以看看这个=>heapq推送类型错误：'<#39；实例之间不支持