链表表示非负整数相加异常：Java解法测试用例报错求助

我来帮你分析代码里的问题，然后给出正确的实现方案。

问题回顾 #

题目要求是：

给定两个非空链表，分别表示两个非负整数。数字以逆序存储，每个节点包含一个数字。将这两个数相加并以链表形式返回。可假设除数字0本身外，两数均无前置零。

示例：

• 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
• 输出：7 -> 0 -> 8
• 解释：342 + 465 = 807

你的解法在这个测试用例上出了问题：

• 输入：[9]、[1,9,9,9,9,9,9,9,9,9]
• 你的输出：[0,-4,-6,-3,-8,-4,-7,-4,-1,-2]
• 预期输出：[0,0,0,0,0,0,0,0,0,0,1]

链表定义（Java） #

public class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

你的错误解法 #

import java.lang.Math;
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        int count = 0;
        int number1=0;
        int number2=0;
        int temp=0;
        while(l1 !=null) {
            temp = l1.val;
            number1 += temp*Math.pow(10,count);
            count++;
            l1= l1.next;
        }
        count = 0;
        while(l2 !=null) {
            temp = l2.val;
            number2 += temp*Math.pow(10,count);
            count++;
            l2= l2.next;
        }
        int sum = number1 + number2;
        ListNode l3 = new ListNode(sum%10);
        ListNode l4 = l3;
        while(sum!=0) {
            sum=sum/10;
            if (sum!=0) {
                l3.next = new ListNode(sum%10);
                l3=l3.next;
            }
        }
        return l4;
    }
}

错误原因分析 #

你的代码有两个致命问题：

1. 整数溢出：Java的int类型最大值是2147483647，而测试用例中的第二个链表对应的数字是9999999991，这个数远远超过了int的范围。当你把这么大的数塞进int变量时，会发生溢出，数值变成负数或者错误的乱码，这就是你得到负数输出的直接原因。

2. 浮点数精度丢失：你用了Math.pow(10, count)来计算位权，但这个方法返回的是double类型。double虽然能表示很大的数，但它的精度有限，当指数较大时（比如count=9，10^9），无法精确表示所有整数，计算temp*Math.pow(10,count)时会出现精度误差，导致number1和number2的数值完全错误。

另外还有一个小漏洞：当相加后最后还有进位时（比如你的测试用例最后需要加一个1），你的循环会因为sum/10变成0而停止，不会创建最后那个节点，不过这个问题被前面的溢出问题掩盖了。

正确的实现方案 #

正确的思路是模拟手工加法的过程：不需要把整个链表转成整数，而是逐位遍历两个链表，计算当前位的和加上进位，生成新节点，同时更新进位。这样既不会有溢出问题，也能完美处理所有边界情况。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 虚拟头节点，简化结果链表的初始化操作
        ListNode dummyHead = new ListNode(0);
        ListNode current = dummyHead;
        int carry = 0; // 进位，初始为0
        
        // 只要有一个链表未遍历完，或者还有进位，就继续循环
        while (l1 != null || l2 != null || carry != 0) {
            // 取出当前位的数值，链表为空则取0
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;
            
            // 计算当前位的总和（包含上一位的进位）
            int sum = val1 + val2 + carry;
            carry = sum / 10; // 更新进位：总和除以10的商
            current.next = new ListNode(sum % 10); // 当前位的数值是总和取余10
            
            // 移动指针，继续下一位
            current = current.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        
        // 返回虚拟头节点的下一个节点，也就是结果链表的第一个有效节点
        return dummyHead.next;
    }
}

代码说明 #

• 虚拟头节点：避免了处理结果链表为空的边界情况，所有新节点都可以通过current.next来创建，逻辑更统一。
• 进位处理：每次计算都带上上一位的进位，确保每一位的和都正确。
• 遍历条件：覆盖了三种情况：l1未遍历完、l2未遍历完、还有进位需要处理，完美解决了两个链表长度不同或者最后有进位的场景（比如你的测试用例最后需要多一个节点存储进位1）。

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