23. 合并 K 个升序链表

迭代

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (!lists.length) {
    return null
  }

  const dummyHead = new ListNode() // 虚拟头结点
  let current = dummyHead // 当前处理的结点也就是链接结尾如果为 null 说明遍历完了

  while (current) {
    let min // 存储本次比较最小的值
    let minIndex  // 存储本次比较最小的值的 index

    for (let i = 0; i < lists.length; i += 1) {
      const node = lists[i]

      // 跳过不存在的值
      if (!node) {
        continue
      }

      // 如果还没有初始化 min 或者有更小的
      // 进行更新
      if (!min || min.val > node.val) {
        minIndex = i;
        min = node
      }
    }

    // 有可能都是 null
    // 知道 min 是哪个了
    if (min) {
      current.next = min // 添加到链接结尾
      lists[minIndex] = min.next // min 所在的值更新为 next
    }

    // 更新最新的 current 指向
    current = current.next
  }

  return dummyHead.next
}

使用最小二叉堆作为优先级队列

function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  if (!lists.length) {
    return null
  }

  const pq = new BinaryHeap<ListNode>((a, b) => a.val - b.val)

  // 初始化优先级队列
  for (let i = 0; i < lists.length; i += 1) {
    const node = lists[i]

    if (node) {
      pq.insert(node)
    }
  }

  const dummyHead = new ListNode()

  // 链表的末尾结点
  let p = dummyHead

  // 队列不为空就一直取
  while (!pq.isEmpty()) {
    // 取出优先级最高的
    const node = pq.extract()

    // 放入下一个需要判断的
    if (node.next) {
      pq.insert(node.next)
    }

    // 添加到链表中
    p.next = node

    // 更新链表的尾部
    p = p.next
  }

  return dummyHead.next
}