链表相加(两数相加)
哪些公司问过
答案要点
- 同时遍历两个链表,用 carry 保存进位,当前位 = sum % 10,进位 = sum / 10
- 链表长度不一致时,较短的一个当作 0
- 用 dummy 哑节点和尾指针构造结果链表
- 循环条件:任一链表未走完或还有进位,最后的进位要新增节点
- 时间 O(max(m,n));正序存储时可用栈或递归
易错点
- 最后的进位漏掉
- 长度不一致时访问空指针
- 进位没有清零或重复累加
- 正序存储时直接按位相加,位对不齐
面试官常见追问
- 如果链表是正序存储,且不能反转链表怎么办?
- 为什么要用 dummy 节点?
- 最后还有进位要怎么处理?
- 可以不用额外空间吗?
完整的口述示范答案、每个追问的参考回答,在启面刷题中心查看;也可以让 AI 面试官用语音按这道题连环追问你。
相关面试题
- 链表的几种经典操作247 场
- 判断链表是否有环70 场
- 合并 K 个有序链表45 场
- Y 型链表找第一个相交节点21 场
- 链表反转及其变形20 场
- 链表重排(找中点、反转、合并)20 场
- K 个一组翻转链表17 场
- 删除链表的倒数第 N 个节点15 场
- 链表排序:归并排序与快速排序9 场
- 链表每两个节点翻转8 场