23.合并k个升序序链表- 力扣（LeetCode）
题目：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6
示例 2：
输入：lists = []
输出：[]
示例 3：
输入：lists = [[]]
输出：[]
提示：
-
k == lists.length
-
0 <= k <= 10^4
-
0 <= lists[i].length <= 500
-
-10^4 <= listsi <= 10^4
-
lists[i] 按 升序 排列
-
lists[i].length 的总和不超过 10^4
思路如下：
方法一：最小堆
合并后的第一个节点 first，一定是某个链表的头节点（因为链表已按升序排列）。
合并后的第二个节点，可能是某个链表的头节点，也可能是 first 的下一个节点。
例如有三个链表 1->2->5, 3->4->6, 4->5->6，找到第一个节点 1 之后，第二个节点不是另一个链表的头节点，而是节点 1 的下一个节点 2。
按照这个过程继续思考，每当我们找到一个节点值最小的节点 x，就把节点 x.next 加入「可能是最小节点」的集合中。
因此，我们需要一个数据结构，它支持：
-
从数据结构中找到并移除最小节点。
-
插入节点。
这可以用最小堆实现。初始把所有链表的头节点入堆，然后不断弹出堆中最小节点 x，如果 x.next 不为空就加入堆中。循环直到堆为空。把弹出的节点按顺序拼接起来，就得到了答案。
注意：
问题：当多个节点的 val 相同时，Python 尝试比较 ListNode 对象，但未定义比较规则会报错。
修复：在元组中增加 index 作为次要排序键，确保即使 val 相同，堆也能正确比较。
方法二：分治（迭代）
结合21题思路，直接自底向上合并链表：
-
两两合并：把 lists[0] 和 lists[1] 合并，合并后的链表保存在 lists[0] 中；把 lists[2] 和 lists[3] 合并，合并后的链表保存在 lists[2] 中；依此类推。
-
四四合并：把 lists[0] 和 lists[2] 合并（相当于合并前四条链表），合并后的链表保存在 lists[0] 中；把 lists[4] 和 lists[6] 合并，合并后的链表保存在 lists[4] 中；依此类推。
-
八八合并：把 lists[0] 和 lists[4] 合并（相当于合并前八条链表），合并后的链表保存在 lists[0] 中；把 lists[8] 和 lists[12] 合并，合并后的链表保存在 lists[8] 中；依此类推。
-
依此类推，直到所有链表都合并到 lists[0] 中。最后返回 lists[0]。
题解如下：
方法一：最小堆
import heapq # 导入堆模块
class Solution:def mergeKLists(self , lists):""":type: lists: List[ListNode]:rtype: ListNode"""# write code here# 初始化堆，存储 (节点值, 唯一索引, 节点) 的元组h = []index = 0 # 全局唯一索引，确保相同值时堆能正确比较for node in lists:if node: # 过滤空链表heapq.heappush(h,(node.val, index, node)) # 将节点值、索引、节点存入堆（按值排序）index += 1 # 索引递增，保证唯一性dummy = ListNode(0)cur = dummywhile h:val,idx,node = heapq.heappop(h) # 使用 idx 接收弹出索引cur.next = node # 将节点连接到结果链表cur = cur.next # 移动当前指针# 若当前节点有后继节点，将其加入堆if node.next:heapq.heappush(h, (node.next.val, index, node.next))index += 1 # 全局索引递增return dummy.next # 返回合并后的链表头方法二：分治（迭代）
class Solution:def mergeKLists(self, lists):""":type: lists: List[Optional[ListNode]]:rtype: Optional[ListNode]"""m = len(lists)if m == 0:return None # 空列表直接返回 Nonestep = 1while step < m: # 分治合并循环# 遍历合并相邻的两个链表，间隔为 step*2for i in range(0, m - step, step * 2):lists[i] = self.mergeTwoLists(lists[i], lists[i + step])step *= 2 # 合并范围扩大一倍return lists[0] # 最终合并结果在 lists[0]# 21. 合并两个有序链表def mergeTwoLists(self, list1, list2):""":type: list1: Optional[ListNode], list2: Optional[ListNode]:rtype: Optional[ListNode]"""cur = dummy = ListNode() # 用哨兵节点简化代码逻辑while list1 and list2:if list1.val < list2.val:cur.next = list1 # 把 list1 加到新链表中list1 = list1.nextelse: # 注：相等的情况加哪个节点都是可以的cur.next = list2 # 把 list2 加到新链表中list2 = list2.nextcur = cur.nextcur.next = list1 if list1 else list2 # 拼接剩余链表return dummy.next