合并K个升序链表

问题

给定一个链表数组，每个链表都已按升序排列。将所有链表合并到一个升序链表中并返回。

示例 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 <= lists[i][j] <= 10^4
• lists[i] 按升序排列
• lists[i].length 的总和不超过 10^4

解答

方法一：最小堆（优先队列）

使用最小堆维护 k 个链表的当前最小节点，每次取出最小值加入结果链表。

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */

class MinHeap {
  constructor() {
    this.heap = [];
  }
  
  push(node) {
    this.heap.push(node);
    this.bubbleUp(this.heap.length - 1);
  }
  
  pop() {
    if (this.heap.length === 0) return null;
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }
  
  bubbleUp(index) {
    while (index > 0) {
      const parentIndex = Math.floor((index - 1) / 2);
      if (this.heap[index].val >= this.heap[parentIndex].val) break;
      [this.heap[index], this.heap[parentIndex]] = [this.heap[parentIndex], this.heap[index]];
      index = parentIndex;
    }
  }
  
  bubbleDown(index) {
    while (true) {
      let minIndex = index;
      const leftChild = 2 * index + 1;
      const rightChild = 2 * index + 2;
      
      if (leftChild < this.heap.length && this.heap[leftChild].val < this.heap[minIndex].val) {
        minIndex = leftChild;
      }
      if (rightChild < this.heap.length && this.heap[rightChild].val < this.heap[minIndex].val) {
        minIndex = rightChild;
      }
      if (minIndex === index) break;
      
      [this.heap[index], this.heap[minIndex]] = [this.heap[minIndex], this.heap[index]];
      index = minIndex;
    }
  }
  
  isEmpty() {
    return this.heap.length === 0;
  }
}

var mergeKLists = function(lists) {
  const heap = new MinHeap();
  
  // 将所有链表的头节点加入堆
  for (const head of lists) {
    if (head) heap.push(head);
  }
  
  const dummy = new ListNode(0);
  let current = dummy;
  
  // 不断取出最小节点
  while (!heap.isEmpty()) {
    const minNode = heap.pop();
    current.next = minNode;
    current = current.next;
    
    // 如果该节点有后续节点，加入堆
    if (minNode.next) {
      heap.push(minNode.next);
    }
  }
  
  return dummy.next;
};

方法二：分治合并

两两合并链表，类似归并排序的思想。

var mergeKLists = function(lists) {
  if (lists.length === 0) return null;
  
  // 两两合并，直到只剩一个链表
  while (lists.length > 1) {
    const merged = [];
    for (let i = 0; i < lists.length; i += 2) {
      const l1 = lists[i];
      const l2 = i + 1 < lists.length ? lists[i + 1] : null;
      merged.push(mergeTwoLists(l1, l2));
    }
    lists = merged;
  }
  
  return lists[0];
};

function mergeTwoLists(l1, l2) {
  const dummy = new ListNode(0);
  let current = dummy;
  
  while (l1 && 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 || l2;
  return dummy.next;
}

关键点

• 最小堆方法时间复杂度 O(N log k)，N 为所有节点总数，k 为链表数量
• 分治方法时间复杂度 O(N log k)，空间复杂度更优
• 最小堆需要维护 k 个元素，每次插入和删除操作为 O(log k)
• 分治方法每轮合并链表数量减半，共需 log k 轮
• 使用虚拟头节点简化链表操作