（LeetCode）两数相加深入分析Java版

两数相加（题目如下）

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例 1：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：

输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：

输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

提示：

每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零

1.如何分析该题目

首先看到这是两个链表

将两个链表看成是相同长度的进行遍历，如果一个链表较短则在前面补 0，比如 987 + 23 = 987 + 023 = 1010
每一位计算的同时需要考虑上一位的进位问题，而当前位计算结束后同样需要更新进位值
如果两个链表全部遍历完毕后，进位值为 1，则在新链表最前方添加节点 1

也就是说：需要添加两个预先指针，这两个预先指针用于以后得新链表构建做了准备。

然后创建进位变量，对与两数相加后大于10做进位做准备。

接着遍历两个链表l1和l2，获取每个节点的value，进行相加，并存放在sum里面，并且进行计算sum%10和sum/10的数值，这两个数值分别对应着一个是即将填写到新链表的数字，另一个是如果sum大于10所进的位的数。

然后将预指针2向后移位并且赋值value，也就是将sum填入进去。

最后也将进位所剩下的值赋予预指针的下一位节点中，用于进行下一次相加。

最后返回新链表的头节点即可得出结果

代码如下所示

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {//定义一个新联表伪指针，用来指向头指针，返回结果ListNode prev = new ListNode(0);//定义一个进位数的指针，用来存储当两数之和大于10的时候，int carry = 0;//定义一个可移动的指针，用来指向存储两个数之和的位置ListNode cur = prev;//当l1 不等于null或l2 不等于空时，就进入循环while(l1!=null || l2!=null){//如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数int x= l1 !=null ? l1.val : 0;//如果l1 不等于null时，就取他的值，等于null时，就赋值0，保持两个链表具有相同的位数int y = l2 !=null ? l2.val : 0;//将两个链表的值，进行相加，并加上进位数int sum = x + y + carry;//计算进位数carry = sum / 10;//计算两个数的和，此时排除超过10的请况（大于10，取余数）sum = sum % 10;//将求和数赋值给新链表的节点，//注意这个时候不能直接将sum赋值给cur.next = sum。这时候会报，类型不匹配。//所以这个时候要创一个新的节点，将值赋予节点cur.next = new ListNode(sum);//将新链表的节点后移cur = cur.next;//当链表l1不等于null的时候，将l1 的节点后移if(l1 !=null){l1 = l1.next;}//当链表l2 不等于null的时候，将l2的节点后移if(l2 !=null){l2 = l2.next;} }//如果最后两个数，相加的时候有进位数的时候，就将进位数，赋予链表的新节点。//两数相加最多小于20，所以的的值最大只能时1if(carry == 1){cur.next = new ListNode(carry);}//返回链表的头节点return prev.next;}
}