合并 K 个有序链表
哪些公司问过
答案要点
- 小顶堆:K 个头节点入堆,弹出最小节点,再把其 next 入堆;时间 O(N log K),空间 O(K)
- 分治:两两合并,一轮后链表数减半,递归到只剩一个;时间 O(N log K)
- 基础操作:合并两个有序链表,用虚拟头节点加双指针,O(n+m)
- 暴力全部排序 O(N log N),不是最优
- 注意空链表、K 为 0 的边界
易错点
- 忘了把弹出节点的下一个节点入堆
- 堆里放的是值而不是节点,丢失了链表信息
- 不处理空链表
- 说分治的时间复杂度是 O(NK)
面试官常见追问
- 为什么顺序逐个合并不如分治?
- 堆的做法需要自定义什么?
- 如果链表非常长,内存放不下怎么办?
- 怎么合并两个有序链表?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场
- 旋转链表:向右移动 k 位8 场