题目链接：2.两数相加

1 原题描述：

2 解题思路

初看此题，其实并不难理解，我们只需要简单对加法过程进行一个模拟，即可完成。那么我们应该怎么模拟呢？首先观察题目，链表是采用的 逆序 存储，这很明显是为了方便我们进行 进位，这样我们可以按照链表的顺序，将两个链表的当前值相加，相加后的值为sum 。sum % 10 即为当前位数的值，sum / 10 即为进位的值。因为考虑到有进位的情况，我们不能直接写 sum=l1.val+l2.valsum = l1.val + l2.valsum=l1.val+l2.val 而是应该写成 sum+=l1.val+l2.valsum += l1.val + l2.valsum+=l1.val+l2.val，这样就可以把进位的值加入。为了确保第一次相加时不被进位影响，我们只需要将 sum 的 初始值 设为 0 即可。对于链表最后一位相加后还有进位的情况，我们只需要在两个链表走完后，判断一下 sum 是否为1，若为1将其再插入。

基础的逻辑我们理顺了，那么我们现在要考虑一个特殊情况了。前面我们思考的时候都是假定两个链表的长度相等，那如果两个链表不等长呢？因此在相加循环的时候，若一个链表走到了末尾变成了null，那么我们就要停止相加。然后判断两个链表谁还有值，再将其剩下的值直接拼接上即可。（注意：此处我们依然要考虑进位的情况，例如 99+199 + 199+1，两个链表长度相等的部分9+1=109 + 1 = 109+1=10，产生了进位，拼接99剩下的一个9时也需要把这个进位考虑到。）

逻辑理顺了，那就让我们来看看代码吧，实现代码如下。可能大家对代码两处有疑点，一是为什么要声明两个链表 res 和 res1 ? 因为该链表结构为单向，我们只能往下走，而不能往回走，因此res 是用来记录我们相加后的值的链表是从哪里开始的，res2 是用来添加我们计算出来的新值的。第二个疑点可能是，为什么返回的是 res.next 而不是 res ？正如前文所述，我们 res 是用来记录链表是哪里开始的，而我们 res 的初始值是我们随便 赋予 的一个0，真正的结果是从 res.next 开始的。

代码实现1：

/*** 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 res = new ListNode(0);ListNode res2 = res;int sum = 0;while(l1 != null && l2 != null){sum += l1.val + l2.val;res2.next = new ListNode(sum % 10);res2 = res2.next;sum /= 10;l1 = l1.next;l2 = l2.next;}while(l1 != null){sum += l1.val;res2.next = new ListNode(sum % 10);res2 = res2.next;sum /= 10;l1 = l1.next;}while(l2 != null){sum += l2.val;res2.next = new ListNode(sum % 10);res2 = res2.next;sum /= 10;l2 = l2.next;}if (sum != 0){res2.next = new ListNode(sum % 10);}return res.next;}
}

虽然说，如上的思路很简单，但整个代码很繁琐，一点也不优雅。那我们还有其他思路吗？我们可以发现，每一个 l.next 都还有自己的 next，那我们是不是可以利用递归，计算出最后一个 next 然后以此返回给上一个 next 呢？

答案是肯定的，那我们应该怎么判断递归是否结束了呢？什么时候不需要接着往下继续传值呢？我们分析一下，首先 l1 或者 l2 只要有一个不为空，那么我就要继续调用下去。对此可能有小伙伴有疑问了，针对两个链表若只有一个为空时，我们应该怎么相加呢？其实很简单，对于为空的情况下我们只需要 new 一个为 0 的节点就行了。除了上面说的这个情况，还有两个链表都为 null 但我还能进位的情况下（即 sum>=10sum >= 10sum>=10)，也需要继续计算。

那么很轻松的，我们递归实现的代码也就出来了！

代码实现2：

/*** 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) {int sum = l1.val + l2.val;ListNode res = new ListNode(sum % 10);if(l1.next != null || l2.next != null || sum >= 10){if (l1.next != null) l1 = l1.next;else l1 = new ListNode(0);if (l2.next != null) l2 = l2.next;else l2 = new ListNode(0);l1.val += sum / 10;res.next = addTwoNumbers(l1, l2);}return  res;}
}