知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 25 - 合并K个升序链表 ## 题目(LeetCode 23) 合并 k 个升序链表,返回合并后的排序链表。 ## 解法:优先队列(小顶堆) ```java class Solution { public ListNode mergeKLists(ListNode[] lists) { PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val); for (ListNode node : lists) if (node != null) pq.offer(node); ListNode dummy = new ListNode(0), cur = dummy; while (!pq.isEmpty()) { ListNode node = pq.poll(); cur.next = node; cur = cur.next; if (node.next != null) pq.offer(node.next); } return dummy.next; } } ``` > 💬 **Q:给出其他解法** > > 还有两种经典解法: > > --- > > **解法二:分治归并(推荐,O(n log k))** > > 思路:把 k 个链表两两配对合并,每轮合并后链表数量减半,类似归并排序。 > > ```java > class Solution { > public ListNode mergeKLists(ListNode[] lists) { > if (lists.length == 0) return null; > return mergeRange(lists, 0, lists.length - 1); > } > > // 分治:合并 [left, right] 范围内的链表 > private ListNode mergeRange(ListNode[] lists, int left, int right) { > if (left == right) return lists[left]; > int mid = (left + right) / 2; > ListNode l1 = mergeRange(lists, left, mid); > ListNode l2 = mergeRange(lists, mid + 1, right); > return mergeTwoLists(l1, l2); > } > > 💬 **Q:这里为什么不能是 `mergeRange(list, left, middle-1)` 和 `mergeRange(list, middle, right)`?** > > 因为 `mid = (left + right) / 2` 是**向下取整**,mid 偏左。如果用 `[left, mid-1]` + `[mid, right]` 划分,当只有两个元素时会死循环: > > - 假设 `left=0, right=1` → `mid = 0` > - 左半:`mergeRange(0, -1)` — 越界或空 > - 右半:`mergeRange(0, 1)` — **和原调用完全相同,无限递归!** > > 而用 `[left, mid]` + `[mid+1, right]`: > - 左半:`mergeRange(0, 0)` → 命中 base case > - 右半:`mergeRange(1, 1)` → 命中 base case > > **规律总结:** > - `mid = (left + right) / 2`(向下取整)→ 必须配 `[left, mid]` + `[mid+1, right]` > - 如果想用 `[left, mid-1]` + `[mid, right]`,则 mid 必须**向上取整**:`mid = (left + right + 1) / 2`,这样才能保证右半部分不退化为原区间 > > // 合并两个有序链表(经典操作) > private ListNode mergeTwoLists(ListNode l1, ListNode l2) { > ListNode dummy = new ListNode(0), cur = dummy; > while (l1 != null && l2 != null) { > if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } > else { cur.next = l2; l2 = l2.next; } > cur = cur.next; > } > cur.next = (l1 != null) ? l1 : l2; > return dummy.next; > } > } > ``` > > --- > > **解法三:逐一合并(最简单,O(nk))** > > 思路:把第一个链表当作结果,依次把后面每个链表合并进来。 > > ```java > class Solution { > public ListNode mergeKLists(ListNode[] lists) { > ListNode result = null; > for (ListNode list : lists) { > result = mergeTwoLists(result, list); > } > return result; > } > > private ListNode mergeTwoLists(ListNode l1, ListNode l2) { > ListNode dummy = new ListNode(0), cur = dummy; > while (l1 != null && l2 != null) { > if (l1.val <= l2.val) { cur.next = l1; l1 = l1.next; } > else { cur.next = l2; l2 = l2.next; } > cur = cur.next; > } > cur.next = (l1 != null) ? l1 : l2; > return dummy.next; > } > } > ``` > > --- > > **三种解法对比:** > > | 解法 | 时间复杂度 | 空间复杂度 | 特点 | > |------|-----------|-----------|------| > | 优先队列 | O(n log k) | O(k) | 堆始终只有 k 个元素 | > | 分治归并 | O(n log k) | O(log k) 递归栈 | 空间最优,思路优雅 | > | 逐一合并 | O(nk) | O(1) | 最简单,但慢 | > > n 是所有节点总数,k 是链表数量。优先队列和分治归并时间复杂度相同,分治归并空间更优,面试中两种都值得掌握。 ## 复杂度 - 时间 O(N log k),N 为总节点数,空间 O(k) ## 一句话总结 小顶堆维护 k 个链表的当前最小节点,每次弹出最小的接上。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入