链表的几种经典操作
哪些公司问过
答案要点
- 反转链表:三指针迭代(prev、cur、next),O(n) 时间、O(1) 空间;也可递归
- 环检测:快慢指针,快走两步慢走一步,相遇即有环;再从头和相遇点同速前进,相遇处是环入口
- 合并有序链表:虚拟头节点加逐个比较,O(n+m)
- 删除重复元素:有序链表比较当前与下一个节点的值并跳过;全部删除用虚拟头节点加 prev
- 删除倒数第 N 个:虚拟头节点,快指针先走 N 步,再同步走到最后一个节点,慢指针即目标的前一个
易错点
- 不处理空链表和单节点链表
- 反转时丢失 next 指针,导致链表断开
- 删除头节点时没有虚拟头节点,忘了更新头指针
- 找环入口只会背结论,不会推导
面试官常见追问
- 为什么快慢指针一定会相遇?
- 怎么找到环的入口?
- 怎么判断两个链表是否相交?
- 只知道要删除的节点指针,怎么删?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场
- 旋转链表:向右移动 k 位8 场