单链表的归并排序
哪些公司问过
答案要点
- 链表适合归并:不需要随机访问,合并只改指针
- 找中点:快慢指针,在中点断开成两半
- 递归排序两半,再用哑节点双指针合并两个有序链表
- 时间 O(n log n),递归栈 O(log n);自底向上按长度倍增合并可做到 O(1) 空间
- 偶数节点时慢指针停在前半部分末尾,才能正确断开
易错点
- 中点没有断开,导致无限递归
- 两个节点时找中点出错
- 合并时忘了接上剩余部分
面试官常见追问
- 为什么链表排序不用快速排序?
- 合并两个有序链表怎么写?
- 快慢指针找中点要注意什么?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场