描述
给你一个链表数组,每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中,返回合并后的链表。
示例 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
# 为了避免相同值的结点无法比较,每个结点配有独一的id
id = 0
for head in lists:
if(not head): continue
heappush(node_heap,(head.val,id,head))
id += 1
while(node_heap):
node = heappop(node_heap)[2]
if(node.next):
heappush(node_heap,(node.next.val,id,node.next))
id += 1
dnode.next = node
dnode = dnode.next
return 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.val
node_heap = []
dummy_node = ListNode(114514)
dnode = dummy_node
for 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 = node
dnode = dnode.next
return dummy_node.next
不过这种性能似乎没之前那个好