一、题目描述2. 两数相加给你两个非空的链表表示两个非负的整数。它们每位数字都是按照逆序的方式存储的并且每个节点只能存储一位数字。请你将两个数相加并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外这两个数都不会以 0 开头。示例 1输入l1 [2,4,3]l2 [5,6,4]输出[7,0,8]解释342 465 807示例 2输入l1 [0]l2 [0]输出[0]示例 3输入l1 [9,9,9,9,9,9,9]l2 [9,9,9,9]输出[8,9,9,9,0,0,0,1]提示每个链表中的节点数在范围[1, 100]内0 Node.val 9题目数据保证列表表示的数字不含前导零除了0本身二、解题思路概览由于链表存储的是数字的逆序形式个位在头节点因此我们可以模拟竖式加法从低位向高位逐位相加同时处理进位。这是最自然、最高效的思路。解法时间复杂度空间复杂度特点模拟加法迭代O(max(m,n))O(max(m,n))标准解法无溢出风险面试首选模拟加法递归O(max(m,n))O(max(m,n))代码简洁递归栈空间先转整数再相加不可行不可行❌ 链表最长100位整数溢出绝不推荐三、解法一模拟加法迭代⭐3.1 思路同时遍历两个链表对应节点值相加再加上进位carry。当前位结果 和 % 10新进位 和 / 10。当两个链表都遍历完且进位为0时结束。3.2 代码实现javaclass Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummy new ListNode(0); // 哑结点 ListNode cur dummy; int carry 0; // 进位 while (l1 ! null || l2 ! null || carry ! 0) { int sum carry; if (l1 ! null) { sum l1.val; l1 l1.next; } if (l2 ! null) { sum l2.val; l2 l2.next; } cur.next new ListNode(sum % 10); cur cur.next; carry sum / 10; } return dummy.next; } }3.3 图解示例输入l1 [2,4,3]342l2 [5,6,4]465步骤l1当前值l2当前值进位carry和sum新节点值新进位1250770246010013341880结束nullnull0---结果链表7 → 0 → 8✅3.4 复杂度分析时间复杂度O(max(m, n))只需遍历较长的链表一次。空间复杂度O(max(m, n))结果链表需要存储所有位。四、解法二模拟加法递归4.1 思路递归函数接收两个链表节点和进位值返回相加后的节点。递归终止条件两个节点均为 null 且进位为 0。4.2 代码实现javaclass Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { return add(l1, l2, 0); } private ListNode add(ListNode l1, ListNode l2, int carry) { if (l1 null l2 null carry 0) { return null; } int sum carry; if (l1 ! null) { sum l1.val; l1 l1.next; } if (l2 ! null) { sum l2.val; l2 l2.next; } ListNode node new ListNode(sum % 10); node.next add(l1, l2, sum / 10); return node; } }4.3 复杂度分析时间复杂度O(max(m, n))空间复杂度O(max(m, n))递归调用栈深度等于结果链表长度。4.4 递归 vs 迭代维度迭代递归代码长度适中极简空间效率O(1)不计结果O(n)栈空间可读性直观需要理解递归风险无链表过长可能栈溢出五、扩展思考5.1 如果链表是正序存储高位在头节点怎么办例如l1 [3,4,2]342l2 [4,6,5]465。此时需要先反转链表再相加最后将结果反转回来。或者使用栈来处理。5.2 如果要求不修改原链表上述两种解法都没有修改原链表只是读取值符合要求。5.3 如果链表表示的数字非常大超过1000位本解法完全不受影响因为它是一位一位处理的不依赖整数类型。这也是该解法相对于“转整数法”的核心优势。六、解法对比与总结方法时间复杂度空间复杂度是否利用逆序存储溢出风险面试推荐度迭代模拟O(max(m,n))O(max(m,n))✅无⭐⭐⭐⭐⭐递归模拟O(max(m,n))O(max(m,n))✅无⭐⭐⭐⭐转整数法不可行不可行✅严重❌6.1 面试建议必须掌握迭代模拟法这是本题的标准答案代码简洁且鲁棒。递归可以展示你对递归的理解但要注意空间代价。绝对不要提“先转整数再相加”的思路除非面试官主动问及溢出问题你可以分析其缺陷。6.2 常见错误忘记处理最后的进位例如[5] [5]应输出[0,1]如果循环条件只判断l1 ! null || l2 ! null就会丢失进位。创建新节点时直接使用sum而不是sum % 10。没有正确移动指针容易忘记l1 l1.next等操作。七、相关链接题目链接2. 两数相加 - 力扣LeetCode官方题解两数相加官方题解