题目：
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 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 = dummy
while 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 # 空列表直接返回 None
step = 1
while step < m: # 分治合并循环
# 遍历合并相邻的两个链表，间隔为 step*2
for 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.next
else: # 注：相等的情况加哪个节点都是可以的
cur.next = list2 # 把 list2 加到新链表中
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2 # 拼接剩余链表
return dummy.next