Algorithms first

合并 K 个升序链表 · 交互式算法学习

合并 k 条升序链表。

#23 · 分治

合并 K 个升序链表

Merge k Sorted Lists

测试用例lists = [[1,4,5],[1,3,4],[2,6]]

栈 / 队列 / 堆3 个关键状态

进度 1 / 3速度

步骤 1三条链表头 1、1、2 入堆。heap size=3

最小堆维护 k 个头

时间 O(N log k)空间 O(k)

堆中始终只放每条链表当前最小头节点。

1function mergeKLists(lists) {2  const heap = [];3  const push = n => {4    heap.push(n);5    let i = heap.length - 1;6    while (i) {7      const p = (i - 1) >> 1;8      if (heap[p].val <= heap[i].val) break;9      [heap[p], heap[i]] = [heap[i], heap[p]];10      i = p11    }12  };13  const pop = () => {14    const top = heap[0],15      last = heap.pop();16    if (heap.length) {17      heap[0] = last;18      for (let i = 0;;) {19        let best = i,20          l = i * 2 + 1,21          r = l + 1;22        if (l < heap.length && heap[l].val < heap[best].val) best = l;23        if (r < heap.length && heap[r].val < heap[best].val) best = r;24        if (best === i) break;25        [heap[i], heap[best]] = [heap[best], heap[i]];26        i = best27      }28    }29    return top30  };31  for (const n of lists)32    if (n) push(n);33  const d = {34    next: null35  };36  let p = d;37  while (heap.length) {38    const n = pop();39    p = p.next = n;40    if (n.next) push(n.next)41  }42  p.next = null;43  return d.next;44}

多语言参考

Java · C++ · Go

来源 · CC BY-SA 4.0 ↗

这是一组同题正确实现，独立于上方当前动画方法；不同语言可能采用另一种正确策略。

1/**2 * Definition for singly-linked list.3 * public class ListNode {4 *     int val;5 *     ListNode next;6 *     ListNode() {}7 *     ListNode(int val) { this.val = val; }8 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }9 * }10 */11class Solution {12    public ListNode mergeKLists(ListNode[] lists) {13        PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);14        for (ListNode head : lists) {15            if (head != null) {16                pq.offer(head);17            }18        }19        ListNode dummy = new ListNode();20        ListNode cur = dummy;21        while (!pq.isEmpty()) {22            ListNode node = pq.poll();23            if (node.next != null) {24                pq.offer(node.next);25            }26            cur.next = node;27            cur = cur.next;28        }29        return dummy.next;30    }31}

交互式算法学习

从执行步骤真正理解 LeetCode 经典 150

本站整理 150 道高频算法面试题和 302 种解法。动画方法同步展示 JavaScript 与 Python；每题另提供 Java、C++ 与 Go 同题参考实现。

多形态可视化数组、矩阵、DP 表、递归树、树图、链表、栈队列堆、区间和状态机按解法选择。

动画与代码同步当前状态、步骤说明、变量和代码高亮保持一一对应，可逐步播放和回退。

适合面试复习每种方案都给出思路、时间复杂度、空间复杂度、测试用例和 LeetCode 中文原题入口。

AlgoViz Lab

合并 K 个升序链表 · 解法对比

AlgoViz Lab2026-07-112026-07-12

合并 k 条升序链表。

测试用例: lists = [[1,4,5],[1,3,4],[2,6]]
题目分类: 分治
解法对比: 2

方案 1

收集全部值排序

收集所有节点值排序，再构造结果链。

时间: O(N log N)
空间: O(N)

方案 2

最小堆维护 k 个头

堆中始终只放每条链表当前最小头节点。

时间: O(N log k)
空间: O(k)