字母链表消除相邻重复对后输出
哪些公司问过
答案要点
- 规则:相邻两个相同字母成对消除,消除后新相邻的继续消
- 用示例验证规则:abbcddceaeffe 最终得到 aea
- 栈解法:与栈顶相同则弹出,否则入栈,O(n) 时间
- 链表可用结果链表头部充当栈,最后反转,额外空间 O(1)
- 确认边界:三个连续相同、全部消光、空链表
易错点
- 误以为是按出现次数奇偶过滤字母
- 只做一轮扫描删除相邻对,漏掉消除后新形成的相邻对
- 在链表上原地删除时指针处理出错,丢失后续节点
面试官常见追问
- 如果规则改成连续 k 个相同才消除呢?
- 为什么不能只统计每个字母出现次数的奇偶?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场