合并K个升序链表

题目描述
给定一个包含 K 个升序链表的数组，每个链表中的元素已经按升序排列。要求将所有这些链表合并成一个新的升序链表，并返回新链表的头节点。

解题思路

1. 暴力法（直接合并）

   • 依次将每个链表合并到结果链表中，即每次合并两个链表。
   • 时间复杂度：假设每个链表平均长度为 n，第一次合并：n + n = 2n，第二次合并：2n + n = 3n，...，第 K-1 次合并：Kn。总时间为 O(n × (2 + 3 + ... + K)) = O(nK²)。
   • 缺点：效率低，适合 K 较小的情况。

2. 分治法（两两合并）

   • 将 K 个链表两两配对，合并每一对，得到 K/2 个新链表；重复此过程，直到只剩一个链表。
   • 合并次数：log₂K 轮，每轮合并所有节点（总节点数 N = nK），因此时间复杂度为 O(N log K)。
   • 空间复杂度：递归深度 O(log K)（若用递归），或 O(1)（若用迭代）。

3. 最小堆（优先队列）优化

   • 维护一个大小为 K 的最小堆，初始时将每个链表的头节点入堆。
   • 每次弹出堆顶节点（当前最小值），将其加入结果链表，并将该节点的下一个节点（若存在）入堆。
   • 时间复杂度：每个节点入堆/出堆一次，堆操作复杂度 O(log K)，总时间 O(N log K)。
   • 空间复杂度：O(K)（堆的大小）。

分治法代码实现（递归）

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def mergeKLists(lists):
    if not lists:
        return None
    if len(lists) == 1:
        return lists[0]
    
    mid = len(lists) // 2
    left = mergeKLists(lists[:mid])   # 递归合并左半部分
    right = mergeKLists(lists[mid:]) # 递归合并右半部分
    return mergeTwoLists(left, right) # 合并两个有序链表

def mergeTwoLists(l1, l2):
    dummy = ListNode(0)
    cur = dummy
    while l1 and l2:
        if l1.val < l2.val:
            cur.next = l1
            l1 = l1.next
        else:
            cur.next = l2
            l2 = l2.next
        cur = cur.next
    cur.next = l1 if l1 else l2
    return dummy.next

最小堆代码实现

import heapq

def mergeKLists(lists):
    heap = []
    # 初始化堆：存入每个链表的头节点（值，链表索引）
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(heap, (node.val, i, node))  # 加入 i 避免比较 ListNode 对象
    
    dummy = ListNode(0)
    cur = dummy
    while heap:
        val, i, node = heapq.heappop(heap)
        cur.next = node
        cur = cur.next
        if node.next:
            heapq.heappush(heap, (node.next.val, i, node.next))  # 下一节点入堆
    return dummy.next

关键点总结

• 分治法通过递归减少合并次数，避免暴力法的高复杂度。
• 最小堆始终维护当前最小节点，适合动态处理流式数据（如多个持续输入的链表）。
• 实际应用中，若 K 较大，优先选择 O(N log K) 的解法。