面试题库 › 客户端 › 单链表的归并排序

单链表的归并排序

难度 ★★☆在 8 场真实面经中被问到 方向:客户端考点:链表

哪些公司问过

腾讯2字节跳动2深信服2百度1网易互娱1

常见岗位:C++ / Qt 客户端、C/C++ 软件开发、安卓、iOS、游戏服务端

答案要点

  1. 链表适合归并:不需要随机访问,合并只改指针
  2. 找中点:快慢指针,在中点断开成两半
  3. 递归排序两半,再用哑节点双指针合并两个有序链表
  4. 时间 O(n log n),递归栈 O(log n);自底向上按长度倍增合并可做到 O(1) 空间
  5. 偶数节点时慢指针停在前半部分末尾,才能正确断开

易错点

面试官常见追问

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

相关面试题