合并K个有序链表

题目

合并K个有序链表

信息

• 类型：问答
• 难度：⭐⭐

考点

堆（优先队列）的应用,链表操作,时间复杂度优化

快速回答

使用最小堆（优先队列）高效合并K个有序链表：

• 初始化最小堆，存储每个链表的头节点（值+节点引用）
• 创建虚拟头节点(dummy)简化链表操作
• 循环从堆中弹出最小节点：
  • 将节点连接到结果链表
  • 若该节点有后继节点，将后继节点入堆
• 时间复杂度优化至O(N log K)，空间复杂度O(K)

问题描述

给定K个升序排列的链表，每个链表长度可能不同。要求将它们合并为一个新的升序链表，并返回头节点。

原理说明

最小堆（优先队列）能高效获取当前K个链表中的最小节点：
1. 堆顶始终是当前所有链表头节点中的最小值
2. 每次取出堆顶节点后，将其后继节点加入堆中
3. 重复过程直到堆为空，时间复杂度O(N log K)，优于暴力解法O(KN)

代码示例（Python）

import heapq

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

def mergeKLists(lists):
    # 最小堆初始化 (避免节点不可比问题)
    heap = []
    for i, node in enumerate(lists):
        if node: 
            heapq.heappush(heap, (node.val, i, node))

    dummy = ListNode()
    curr = dummy

    while heap:
        val, idx, node = heapq.heappop(heap)
        curr.next = node
        curr = curr.next
        if node.next:
            heapq.heappush(heap, (node.next.val, idx, node.next))

    return dummy.next

最佳实践

• 虚拟头节点：简化链表连接操作
• 堆元素设计：存储(val, idx, node)三元组：
  • val用于比较优先级
  • idx确保当val相同时仍可比较
  • node保留链表引用
• 空链表处理：初始化时跳过空链表

常见错误

• 直接比较节点：未封装(val, idx)导致TypeError
• 内存泄漏：忘记断开原链表中的next指针（非必须）
• 忽略空输入：未处理lists为空或包含空链表的情况
• 错误复杂度：误认为时间复杂度是O(N log N)

复杂度分析

• 时间复杂度：O(N log K)
  • N：所有链表总节点数
  • K：链表个数
  • 每个节点进出堆一次，堆操作O(log K)
• 空间复杂度：O(K)（堆的大小）

扩展知识

• 分治解法对比：同样O(N log K)，但空间复杂度O(1)：

  def mergeKLists(lists):
      if not lists: return None
      interval = 1
      while interval < len(lists):
          for i in range(0, len(lists)-interval, interval*2):
              lists[i] = mergeTwo(lists[i], lists[i+interval])
          interval *= 2
      return lists[0]

• 堆优化场景：当K很大但链表长度差异大时，堆解法比分治更优
• 其他语言实现：
  • Java：使用PriorityQueue和Comparator
  • C++：使用priority_queue和自定义比较函数