LeetCode Add Two Numbers JavaScript题返回ListNode类型错误求助

错误原因排查 #

1. 输入输出类型不匹配 #

你完全误解了题目的输入输出结构：

• 输入的l1、l2不是数组，是ListNode链表类的实例，每个节点只有val（当前位数值）和next（指向下一个节点的指针）两个属性，不存在length属性，你用数组的下标遍历方式读取链表本身就会报错。
• 题目要求返回值也是ListNode类型的链表，你直接返回数组，所以触发了报错信息里的is not valid value for the expected return type ListNode类型校验错误。

题目示例里的[2,4,3]只是LeetCode用来可视化链表结构的写法，实际传入的不是数组。

2. 数值精度问题 #

就算你把输入转成数组处理，用parseInt转整数相加的逻辑也有缺陷：JavaScript 中Number类型的安全整数范围是-2^53 ~ 2^53-1，如果输入的链表长度超过16位，转换出来的整数会直接精度丢失，计算结果错误。

正确实现思路 #

按照链表的特性逐位相加，处理进位即可，不需要转整数：

1. 新建虚拟头节点简化链表拼接逻辑，维护进位变量carry初始为0
2. 同时遍历两个链表，每次取当前节点的数值（节点不存在则取0），求和后计算当前位数值和新的进位
3. 把当前位数值封装为新的ListNode节点，拼接到结果链表后
4. 遍历结束后如果还有剩余进位，需要额外加一个节点存储进位
5. 返回虚拟头节点的next作为结果链表的头节点

正确代码 #

function ListNode(val, next) {
    this.val = (val===undefined ? 0 : val)
    this.next = (next===undefined ? null : next)
}

var addTwoNumbers = function(l1, l2) {
    // 虚拟头节点
    const dummy = new ListNode()
    let current = dummy
    let carry = 0

    while(l1 || l2 || carry) {
        const val1 = l1 ? l1.val : 0
        const val2 = l2 ? l2.val : 0
        const sum = val1 + val2 + carry
        // 计算当前位和进位
        carry = Math.floor(sum / 10)
        current.next = new ListNode(sum % 10)
        // 指针后移
        current = current.next
        if(l1) l1 = l1.next
        if(l2) l2 = l2.next
    }

    return dummy.next
}

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