代码随想录算法训练营第三十一天丨23. 合并 K 个升序链表

本文主要是介绍代码随想录算法训练营第三十一天丨23. 合并 K 个升序链表，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

过年闲不下来（太菜了多练练），看算法导论书，做一点题目。

23. 合并 K 个升序链表/习题6.5-9

先贴代码，再总结下遇到的问题。

import heapq
class Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:counter = itertools.count()  # 创建一个无限的递增计数器cur_heap = []dummy_head = ListNode()cur = dummy_headfor item in lists:if item: heapq.heappush(cur_heap, (item.val,next(counter), item))while cur_heap:cur.next = heapq.heappop(cur_heap)[2]cur = cur.nextif cur.next:heapq.heappush(cur_heap, (cur.next.val,next(counter), cur.next))return dummy_head.next

读算法导论书，习题6.5-9正好有一题力扣上也有的题目，做一下。

这章节是优先队列，那这题肯定是优先队列做。遇到的第一个问题是item.val相等时，heapq会去比较元组第二个元素，当时没有引入counter，他就会去比较item本身，listnode在设计时没有比大小功能，学到写法:

import itertoolscounter = itertools.count()

只要调用next(counter)就会一直递增的返回从0开始的数字，解决了heapq不会处理相等的情况。

*当元素具有相同的优先级或值时，heapq 会尝试比较堆中的下一个元素（如果元素是元组或其他可比较的复合结构）。如果整个比较过程中所有可比较的部分都相等，那么 heapq 在没有其他比较依据的情况下，将无法决定两个元素的顺序，可能会引发 TypeError。

第二个问题是for循环创建k个head的时候，必须先确定不是None对象才行。

这么容易就AC一个困难？？？还得是看书才行。

这篇关于代码随想录算法训练营第三十一天丨23. 合并 K 个升序链表的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---