LeetCode两数相加递归实现异常：输入[0]和[1]返回[2]排查

我在做LeetCode的「两数相加」题，题目要求对两个链表的元素逐位相加，示例输入：l1 = [2,4,3]，l2 = [5,6,4]，输出：[7,0,8]。我写了递归实现的代码，但测试输入l1 = [0]、l2 = [1]时，程序返回[2]而非预期的[1]。排查发现carry变量被设为true，但找不到原因，不确定是逻辑问题还是递归导致的异常。

我的代码如下：

let carry = false;
var addTwoNumbers = function(l1, l2) {
    if(l1===null && l2===null){
        return carry? new ListNode(1,undefined):null;
    }
    else if(l1===null){
        let number = carry?  l2.val + 1:l2.val;
        carry = number >= 10;
        number = carry? number-10:number;
        return  new ListNode(number, addTwoNumbers(l1,l2.next));
    }
    else if(l2===null){
        let number = carry?   l1.val + 1:l1.val;
        carry = number >= 10;
        number = carry? number-10:number;
        return  new ListNode(number, addTwoNumbers(l1.next,l2));
    }
    else{
        let number = carry? l1.val + l2.val + 1:l1.val + l2.val;
        carry = number >= 10;
        number = carry? number-10:number;
        return new ListNode(number, addTwoNumbers(l1.next,l2.next));
    }
};

问题原因 #

问题出在全局变量carry。递归调用会共享这个全局状态，一旦之前的测试用例触发过进位（把carry设为true），后续调用函数时carry不会自动重置为初始的false，导致错误地多加1。

比如你测试l1=[0]、l2=[1]时，如果之前的测试残留了carry=true，计算时就会变成0+1+1=2，最终返回节点值为2，和你遇到的情况完全匹配。

修正方案 #

把carry改成递归函数的参数，每次递归传递当前的进位状态，彻底避免全局状态的干扰。修正后的代码逻辑更简洁，分支判断也更统一：

var addTwoNumbers = function(l1, l2, carry = false) {
    // 两个链表都遍历完，处理最后的进位
    if(l1 === null && l2 === null){
        return carry ? new ListNode(1) : null;
    }
    // 获取当前节点的值，空节点则取0
    const val1 = l1 ? l1.val : 0;
    const val2 = l2 ? l2.val : 0;
    // 计算当前位总和与新的进位
    const sum = val1 + val2 + (carry ? 1 : 0);
    const newCarry = sum >= 10;
    const currentVal = newCarry ? sum - 10 : sum;
    // 获取下一个节点，空节点则传null
    const nextL1 = l1 ? l1.next : null;
    const nextL2 = l2 ? l2.next : null;
    // 递归构建下一个节点
    return new ListNode(currentVal, addTwoNumbers(nextL1, nextL2, newCarry));
};

关键修正点 #

• 移除全局carry，改为函数参数并设置默认值false，确保每次函数调用的初始状态正确
• 统一处理空节点的情况，用val1和val2统一取值，简化了原代码的多分支判断
• 每次递归传递新的进位状态newCarry，保证递归链中的状态独立，不会互相干扰

内容的提问来源于stack exchange，提问作者Theo Calianos