听：测试开发面试题解（16）- 两数相加

测试开发面试题解 - 16.两数相加

难度分类

中等

题目描述

给定两个非空链表代表两个非负整数，链表头节点位于数字最高位。每个节点存储单个数字，相加后返回新链表。除了数字0，不以零开头。进阶问题为无法修改输入链表。

算法分析

算法从两个链表的最后一个节点开始相加，较长链表上累加值并记录进位。如果最后有进位，添加新节点作为头节点。具体步骤包括：

• 计算两个链表的长度。
• 用递归对不同长度链表相加，确保递归至最后处理两链表尾节点。
• 分情况处理相加和及进位，递归返回进位值。
• 根据链表长度获得最后进位值，新增节点作头节点或返回较长链表。

代码示例

提供了Python代码实现该算法，包含计算链表长度的函数和递归求和函数。

学习资源

文章末尾提供了免费测试开发试听课链接，强调每天至少2小时学习时间和编写代码的习惯对成功的重要性，并提供了测试开发相关资源。