Hi，大家好，我是Tom。一个美术生转到Java开发的程序员。今天给大家分享的是力扣题第2题，求两数相加。在解题过程中，也会手写一些伪代码。当然，如果想要完整的源码的话，可以到我的个人主页简介中获取。
这道题属于中等难度，通过率只有42%。
1、题干分析
首先，我们来分析一下这道题的题干。
它说，给两个非空的链表，表示两个非负的整数。也就是说，这个链表中的每一个节点中的数都是正整数。然后，它说每位数字都是按照逆序的方式存储的，逆序是什么意思后面再来解释。并且每个节点只能存储一位数字。也就是说，如果得到一个两位数，那就只能存它的个位数，并且要向后一个数进 1。
这里它让你实现的是两个数相加，并且以相同的形式返回一个表示和的链表。这句话什么意思呢？官方也给了几个示例，我们来看一下示例1：
它要求输入2,4,3 和 5,6,4 这两个链表，要求输出7,0,8这样一个结果。这是什么意思呢？意思就是让我们实现342 加上 456 等于 807 的进位运算过程。
我们来看，输入的第1个链表的第1个元素数值2 和 输入的第2个链表的第1个元素数值 5，相加的结果为7，所有暂存到返回结果链表的第1个元素位置。
输入的第2个链表的第2个元素数值4 和 输入的第2个链表的第2个元素数值 6，相加的结果为10。这个时候10，题干中有说到，每个节点只能存储一位数字。因此，只能把10的个位数0暂存到返回结果链表的第2个元素的位置，那么把十位数1只能存到后一个元素的位置，也就是第3个元素。
接下来，继续拿输入的第1个链表的第3个元素数值3 和 输入的第2个链表的第3个元素数值4，相加得到结果为7，把7暂存到返回结果链表的第3个元素的位置。但是前一位运算的时候，已经进了一个十位数1，因此，需要先把原来进上来的1 加上 7等于8，再存到这个位置。所以，返回结果链表的第3个元素值为8。
所以，最终返回的结果链表值为7,0,8。也就是说完整地还原 342 加上 465 等于 807 的进位运算过程。
那对于这道题呢，我给出两种解题方法。第一种方法是迭代法求解，第二种方法是递归法求解。
2、迭代法求解
接下来，我们先来看看如何用迭代法来解决这道题。它的基本实现思路就是，将两个数字的每一位，从左到右依次相加。如果遇到相对的结果是两位数，就只在对应的位置上存储它的个位数，并且把十位数的值往后进 1。
那么，在实现这个逻辑之前，我们先要了解两个运算符号。一个是除号 “ / ”，一个是取模符号 “ % ”。假设我们得到一个相加的结果为12，那么12 除以 10，运算可以得到整除的数为 1，也就是十位数，要往后进 1 的那个的值。同样 12 模以 10 ，运算可以得到余数的值 为 2，也就是个位数的值。
那么，接下来这道题具体如何来求解呢？来看，我准备了两个数分别是 999 和 99。那么，我们从左往右相加，
先拿 9 加 9 等于 18，那么，它的个位数为 8，我们将它暂存起来，然后，十位数是 1，需要往后进 1 位。在迭代过程中，每次进 1 我们需要声明一个变量 nextCarry ，把这个进位的值临时保存一下。
然后，再继续往后运算，9 加 9 等于 18，它的个位数是 8，这个时候，我们发现上一次运算的时候进了一位，所以，我们要拿进位的这个 1 和 8相加之后，再进行存储，因此，存储的值为9。那么它的十位数1，继续往后一位进 1。
然后，继续往后运算，第一个数 9 往下加第二个数没有位置可以加了，所以，就直接把这个就存到结果中去。可是，我们又返现上一次运算结果中进了一位，所以，要拿上次进位的结果加上这次运算的结果的个位数，得到的结果为10，这个时候，又超过了两位数。所以，我们要继续往后进 1，把个位数存起来，十位数往后进 1。
到这个时候，这两个数的相加运算全部完成，得到的结果为8、9、0、1。那实际上，我们前面的题干中有说到，这是一个逆向存储的数。实际上，以上运算的意思就是 999 加上 99 相加得到的结果为 1098。
下面是迭代求解法的伪代码。
3、递归法求解
接下来我们来分析一下，如何用递归法求解。所谓递归法就是同一个方法自己调用自己，知道满足某个条件最后原路返回。它的基本思路是这样的，同样还是准备两个链表 l1 为 999 和 l2 为 99，然后，定义一个result用来缓存要返回的结果链表。当然，也要定义一个保存进位的变量nextCarray。
首先拿两个链表的第1个元素相加，那么得到结果是18，这个时候我们需要把他的个位数缓存到result中，然后十位数要进1，缓存到nextCarray这个变量中。
由于，我们这里用的是递归，需要在进入下一次递归之前把这个进位的值累加到 l1 的下一个节点上，当然，我们可以累加到 l2 上也是没有问题的。那么我们加上之后 l1 的第二个元素的值就等于10了。因为这个nextCarray它是定义在递归方法里面，不是一个全局变量，所以，在进入下一次递归之后，这个nextCarray的值会被覆盖掉。是感知不到上次的进位存在的。所以，我用这种特殊技巧直接把进位值加到 l1 的下一个节点上，然后再进入下一次递归。
当我们，进入下一次递归的时候，发现10 加 9 等于 19，这个时候，我们要做的是将个数 9 存到 result 的下一个节点，然后，把进位数 1 继续加到 l1 的下一个节点上，这个时候， l1 的下一个节点就变成了 10。接着继续下一次递归。
此时，再进入到下一次递归的时候，发现 l2 已经没有元素了。我们需要在 l2 的下一个节点用0作补位，因为，任何数加上 0 对结果是没有影响的。那这个时候，10 加 0 等于 10，个位数是 0 存到 result 的下一个位置，而十位数 nextCarry 还需进 1 。但是 l1 和 l2 都没有元素了，所以，我们需要在 l1 和 l2 上都用 0 作补位，并且把进位数 1 加到 l1 上，，然后，继续下一次递归。
那么，最后一次递归，我们 将 1 加上 0 得到结果为 1，只有个位数，于是将个位数结果 1 存到 result 的下一个位置上为 1，最后，当 l1 和 l2 都没有元素了，而且进位数 nextCarray 也等于 0三个条件同时满足，我们就终止递归，并返回 result 这个链表。
接下来我们来看递归求解法的伪代码。
以上就是我关于两数之和解题思路分享。这道题就算法本身而言是比较简单的，理清思路，逐渐添加判断即可获得解法。重点在于大家是否能够想到通过递归算法来进行解答。本道题递归算法并没有让时间复杂度降低，而在某些情况下通过递归算法能将时间复杂度从O(n)降低到O(logn)，这将是很大性能提升，比如，求x的n次方。如果需要完整代码的小伙伴，可以在我的个人主页简介中获取。
我是被编程耽误的文艺Tom，如果我的分享对你有帮助，请动动手指一键三连分享给更多的人。关注我，面试不再难！
附：完整源码地址：
GitHub
GitEE
