【Python】小顶堆：困难 Leetcode 23. 合并 K 个升序链表 -- Python中heapq对于自定义数据类型的比较

本文主要是介绍【Python】小顶堆：困难 Leetcode 23. 合并 K 个升序链表 -- Python中heapq对于自定义数据类型的比较，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

描述

给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。

示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

代码

代码1

由于可能存在相同值的结点，当用元组或数组作为堆中元素时，会出现无法比较结点的情况。在这里解决的方法是每个元组中再添加进一个独一无二的id

class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:node_heap = []dummy_node = ListNode(-float('inf'))dnode = dummy_node# 为了避免相同值的结点无法比较，每个结点配有独一的idid = 0for head in lists:if(not head): continueheappush(node_heap,(head.val,id,head))id += 1while(node_heap):node = heappop(node_heap)[2]if(node.next):heappush(node_heap,(node.next.val,id,node.next))id += 1dnode.next = nodednode = dnode.nextreturn dummy_node.next

在这里插入图片描述

代码2

来自GPT：
在Python中，__lt__代表“less than”（小于）的缩写。这个特殊方法用于定义对象的“小于”比较运算符(<)的行为。Python中还有其他一些类似的特殊方法，如__gt__（greater than，大于）、__le__（less than or equal to，小于等于）、__ge__（greater than or equal to，大于等于）和__eq__（equal to，等于），它们分别用于定义不同的比较运算符的行为。
通过使用__lt__等方法，Python允许你自定义对象之间的比较行为，这样你就可以使用<、>、<=、>=和==等运算符来比较你的自定义对象。

class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:ListNode.__lt__ = lambda self, other: self.val < other.valnode_heap = []dummy_node = ListNode(114514)dnode = dummy_nodefor head in lists:if(head): heappush(node_heap,head)while(node_heap):node = heappop(node_heap)if(node.next): heappush(node_heap,node.next)dnode.next = nodednode = dnode.nextreturn dummy_node.next