链表排序:归并排序与快速排序
哪些公司问过
答案要点
- 链表不支持随机访问,归并排序最合适
- 快慢指针找中点并断开,递归排序两半,再合并两个有序链表
- 合并用 dummy 头节点,时间 O(n log n),递归栈空间 O(log n)
- 自底向上归并可把空间降到 O(1)
- 快速排序:基准分两条子链再拼接,平均 O(n log n)、最坏 O(n²);插入排序 O(n²)
易错点
- 找中点后没有断开链表,造成死循环
- 合并时没有处理一边先走完的情况
- 对链表用堆排序或下标访问
- 把递归归并的空间说成 O(1)
面试官常见追问
- 怎么找链表的中点?
- 链表归并的时间复杂度是多少?
- 排序之后怎么查找某个特定值?
- 为什么数组常用快排,链表却更适合归并?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表每两个节点翻转8 场
- 旋转链表:向右移动 k 位8 场