题目描述

方法：初等数学

思路

我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。

算法

就像你在纸上计算两个数字的和那样，我们首先从最低有效位也就是列表 l1 和 l2的表头开始相加。由于每位数字都应当处于 0……9 的范围内，我们计算两个数字的和时可能会出现 “溢出”。例如，5+7=12。在这种情况下，我们会将当前位的数值设置为 2，并将进位 carry=1 带入下一次迭代。进位 carry 必定是 0 或 1，这是因为两个数字相加（考虑到进位）可能出现的最大和为 9+9+1=19。

伪代码如下：

请注意，我们使用哑结点来简化代码。如果没有哑结点，则必须编写额外的条件语句来初始化表头的值。

请特别注意以下情况：

Java代码如下：

public static ListNode addTwoNum(ListNode l1, ListNode l2){
        ListNode res=new ListNode(0);//定义一个新的节点用于存储结果
        ListNode temp1=l1;
        ListNode temp2=l2;
        ListNode l3=res;//这里需要用一个临时节点存放结果，不能乱动头结点，否则出错
        int addMore=0;//进位
        //只要两个数有一个非空就可以计算
        while(temp1!=null||temp2!=null){
            //得到每一个节点的值
            int x=temp1!=null?temp1.val:0;
            int y=temp2!=null?temp2.val:0;
            //相加，判断是否有进位，
            // 第一个节点进位，
            // 最后一个节点进位
            int result=(x+y+addMore);
            l3.next=new ListNode(result%10);
            addMore=result/10;
            if(temp1!=null)
            temp1=temp1.next;
            if(temp2!=null)
            temp2=temp2.next;
            l3=l3.next;
        }
        //如果都遍历完成之后判断最后是否还有进位
        if(addMore>0){
            l3.next=new ListNode(addMore);
        }
        //返回头结点之后的，因为头结点之后的才是结果
        return res.next;
    }

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

作者：LeetCode
链接：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
来源：力扣（LeetCode）