面试题库 › 客户端 › 链表排序:归并排序与快速排序

链表排序:归并排序与快速排序

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

哪些公司问过

腾讯1字节跳动1拼多多1百度1vivo1小红书13601多益网络1比特大陆&理想汽车1

常见岗位:人工智能、机器学习算法(泛)、后端开发、C++ 后端、客户端

答案要点

  1. 链表不支持随机访问,归并排序最合适
  2. 快慢指针找中点并断开,递归排序两半,再合并两个有序链表
  3. 合并用 dummy 头节点,时间 O(n log n),递归栈空间 O(log n)
  4. 自底向上归并可把空间降到 O(1)
  5. 快速排序:基准分两条子链再拼接,平均 O(n log n)、最坏 O(n²);插入排序 O(n²)

易错点

面试官常见追问

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

相关面试题