面试题库 › C++ / 后端 › 合并 K 个有序链表

合并 K 个有序链表

难度 ★★★在 45 场真实面经中被问到 方向:C++ / 后端考点:链表

哪些公司问过

美团6字节跳动5腾讯4快手4阿里巴巴4华为2拼多多2百度2蚂蚁集团2小米1京东1亚马逊1

常见岗位:Java 后端、C/C++ 软件开发、大模型算法、推荐搜索广告、C++ 后端

答案要点

  1. 小顶堆:K 个头节点入堆,弹出最小节点,再把其 next 入堆;时间 O(N log K),空间 O(K)
  2. 分治:两两合并,一轮后链表数减半,递归到只剩一个;时间 O(N log K)
  3. 基础操作:合并两个有序链表,用虚拟头节点加双指针,O(n+m)
  4. 暴力全部排序 O(N log N),不是最优
  5. 注意空链表、K 为 0 的边界

易错点

面试官常见追问

完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。

相关面试题