两数相加

这是一道围绕链表、递归、数学展开的高频练习。建议先掌握「链表模拟加法」这套写法，再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。

链表

递归

数学

原题练习

题目分析

这道题表面上是在处理「两数相加」，但先要想清楚题目到底让你返回什么，以及过程中哪些约束必须一直满足。从题型上看，它主要在考链表、递归这些能力。先别急着写代码，先把题目要求翻译成人话，明确结果是什么、约束是什么、过程里要持续维护什么。只有先把题目要求翻译成人话，后面的推荐代码才是在实现思路，而不是直接给答案。

接下来怎么看推荐代码：带着这个理解再看推荐代码时，重点观察这条主线：同时遍历两条链表并维护进位，每一步生成一个新节点，完整模拟竖式加法。

推荐代码

推荐解法：链表模拟加法

时间复杂度： O(max(m,n))

空间复杂度： O(max(m,n))

核心思路：同时遍历两条链表并维护进位，每一步生成一个新节点，完整模拟竖式加法。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode tail = dummy;
        int carry = 0;

        while (l1 != null || l2 != null || carry != 0) {
            int value1 = l1 != null ? l1.val : 0;
            int value2 = l2 != null ? l2.val : 0;
            int sum = value1 + value2 + carry;

            tail.next = new ListNode(sum % 10);
            tail = tail.next;
            carry = sum / 10;

            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }

        return dummy.next;
    }
}

结构化讲解

面试时怎么讲

开场思路

这题我会直接模拟竖式加法，因为链表顺序正好是低位在前。

核心过程

同时遍历两条链表，没有节点的位置按 0 处理。
把两个值和进位相加，当前位生成新节点。
进位更新为 sum / 10，当前位值为 sum % 10。
直到链表和进位都处理完为止。

复杂度总结

时间复杂度 O(max(m,n))，空间复杂度 O(max(m,n))。

面试补一句：这题最关键的是循环条件要覆盖“残留进位”。

核心思路

链表低位在前，正好适合从头开始模拟按位相加。每轮把两个节点值和进位相加，当前位建新节点，十位部分留给下一轮继续处理。

步骤讲解

用哑节点串起结果链表

新链表长度不确定，哑节点可以统一处理头节点创建。

为什么这样做：每一轮都会在尾部追加一个新节点。

对应代码提示：ListNode dummy = new ListNode(0);

按位相加并维护进位

读取两个当前节点值和进位，得到当前位和新的进位。

为什么这样做：这是竖式加法在链表场景中的直接映射。

对应代码提示：int sum = value1 + value2 + carry;

最后处理残留进位

当两条链表都走完后，如果还有进位，需要补一个新节点。

为什么这样做：像 5 + 5 这样的情况会多出一位。

对应代码提示：while (l1 != null || l2 != null || carry != 0) { ... }

易错点

循环条件只写到两条链表都不空

那会漏掉长链表剩余部分，或漏掉最后的进位。

正确理解：循环条件要把 carry != 0 也包含进去。

直接修改原链表节点值

虽然有时能做，但面试里更稳的是构造一条全新结果链表。

正确理解：使用哑节点和尾指针逐步追加新节点。

复杂度与适用判断

时间复杂度：O(max(m,n))

空间复杂度：O(max(m,n))

比其他方案更好在哪里：比先转成整数再相加更符合题目对大数和链表结构的考察。

适用判断：链表表示数字、且低位在前时，通常就是按位模拟加法。

额外提醒

低位在前让你不需要翻转链表，直接从头开始加。