Python如何将ListNode节点存入heap解决合并k个有序链表比较报错

报错原因 #

heapq 对元组进行大小比较时会按顺序逐个对比元素，当两个元组的首个元素（节点val值）相等时，会自动对比元组的第二个元素，也就是你存入的ListNode实例。由于你定义的ListNode类没有实现<运算符对应的比较逻辑，因此触发类型错误，和是否被识别为整个链表无关。

修复方案 #

方案1：添加唯一中间对比值（推荐，无需修改原类定义） #

在入堆元组中插入一个全局唯一的中间值（比如每个链表的遍历索引），保证val相等时只会对比这个唯一值，不会触发ListNode实例的比较逻辑，同时可以过滤空链表避免后续异常。

修复后完整可运行代码如下：

import heapq

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]

heap = []
# 遍历携带索引作为唯一中间值
for idx, l in enumerate(lists):
    if l:
        heapq.heappush(heap, (l.val, idx, l))

# 完整合并逻辑
dummy = ListNode()
current = dummy
while heap:
    val, idx, node = heapq.heappop(heap)
    current.next = node
    current = current.next
    # 将当前节点的下一个节点入堆
    if node.next:
        heapq.heappush(heap, (node.next.val, idx, node.next))

# dummy.next 即为合并后的有序链表头节点

方案2：给ListNode类添加比较方法 #

如果允许修改原节点类定义，可以直接为ListNode实现<比较逻辑，后续直接存入(val, node)也不会报错：

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
    # 实现小于比较逻辑
    def __lt__(self, other):
        return self.val < other.val

内容的提问来源于stack exchange，提问作者flashburn