合并K个排序链表

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

示例：
输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]
解释：将三个链表合并后的升序链表如上所示。

解题思路分析
这个问题是"合并两个有序链表"的扩展。最直观的思路是每次比较所有链表的当前节点，选择最小的节点连接到结果链表中。但这样效率较低（O(kN)，k是链表数量，N是总节点数）。

我们可以使用更高效的方法：

1. 顺序合并：依次合并每个链表，但这样会导致重复比较
2. 分治合并：采用分治策略，两两合并链表
3. 优先队列：使用最小堆来维护当前所有链表的头节点

分步详解

步骤1：基础情况处理

if not lists or len(lists) == 0:
    return None

步骤2：分治合并策略
将k个链表分成两半，递归合并每一半，最后合并两个结果：

def mergeKLists(lists):
    if not lists:
        return None
    
    # 递归合并函数
    def mergeTwoLists(l1, l2):
        dummy = ListNode(0)  # 虚拟头节点
        current = dummy
        
        while l1 and l2:
            if l1.val <= l2.val:
                current.next = l1
                l1 = l1.next
            else:
                current.next = l2
                l2 = l2.next
            current = current.next
        
        # 连接剩余部分
        current.next = l1 if l1 else l2
        return dummy.next
    
    # 分治合并
    def merge(lists, left, right):
        if left == right:
            return lists[left]
        
        mid = (left + right) // 2
        l1 = merge(lists, left, mid)
        l2 = merge(lists, mid + 1, right)
        return mergeTwoLists(l1, l2)
    
    return merge(lists, 0, len(lists) - 1)

步骤3：详细执行过程（以示例为例）
lists = [[1,4,5],[1,3,4],[2,6]]

1. 第一次分治：合并[1,4,5]和[1,3,4]得到[1,1,3,4,4,5]
2. 第二次合并：[1,1,3,4,4,5]和[2,6]合并
3. 最终结果：[1,1,2,3,4,4,5,6]

步骤4：优先队列解法（更直观）

import heapq

def mergeKLists(lists):
    if not lists:
        return None
    
    # 最小堆，存储(val, 链表索引)
    heap = []
    
    # 将所有链表的头节点加入堆
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))
    
    dummy = ListNode(0)
    current = dummy
    
    while heap:
        val, idx, node = heapq.heappop(heap)
        current.next = node
        current = current.next
        
        # 如果当前链表还有下一个节点，加入堆
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))
    
    return dummy.next

复杂度分析

• 时间复杂度：O(Nlogk)，其中N是总节点数，k是链表数量
• 空间复杂度：O(k)（优先队列大小）或O(logk)（分治递归深度）

关键点总结

1. 分治策略将问题规模从k降到logk
2. 优先队列自动维护当前最小节点
3. 虚拟头节点简化链表操作
4. 注意空链表的边界情况处理