两数相加

本题来自力扣官网
难度：中等

给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

一看到这个题目，第一想法就是使用递归。

题目的逻辑理解起来很容易，毕竟小学时候学数学的加法，一开始就是自己手算：个位加个位，十位加十位，百位加百位……如果相加超过十则往前进一位。

使用递归实现起来要比官方给出的解答要麻烦一些，因为方法已经固定好了，所以需要我们自己定义一些类变量来保存计算中需要处理的结果和进位操作。

下面是我写的代码：

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    /* 如果相加超过了10，需要往前进一位 */
    private boolean overTen = false;

    /* 保存需要返回的结果 */
    private ListNode result = null;
    
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 如果两个数都为空了，则返回结果
        if (l1 == null && l2 == null && overTen == false) {
            return result;
        }
        // 如果其中有不为空的则计算
        // 取各自的最后一位数
        int num1 = l1 != null ? l1.val : 0;
        int num2 = l2 != null ? l2.val : 0;
        // 两者相加
        int sum = num1 + num2;
        // 如果上次计算的和超过了10，则当前的计算结果需要加1
        if (overTen) {
            sum += 1;
        }
        // 判断是否大于10
        if (sum >= 10) {
            overTen = true;
            sum -= 10;
        } else {
            overTen = false;
        }

        if (result == null) {
            // 如果是第一次，则需要实例结果，然后添加第一位参数
            result = new ListNode(sum);
        } else {
            // 如果不是第一次，则循环找到最后一位
            result.next = createNext(result.next, sum);
        }
        addTwoNumbers(l1 != null ? l1.next : null, l2 != null ? l2.next : null);
        return result;
    }
    
    /**
     * 创建下一个结果
     */
    private ListNode createNext(ListNode next, int num) {
        if (next == null) next = new ListNode(num);
        else next.next = createNext(next.next, num);
        return next;
    }
}

计算的逻辑是很快就想好了，也是正确的，但是期间出了一个问题一直卡住，就是ListNode.next的对象传递，也是自己基础不够夯实，一直把自己给绕进去了，返回的结果永远没有下一位（只有一位数）。

后来也是想着通过递归来解决这个问题：一直递归next属性，如果为空了则说明是最后一位了，触底创建结果，往上返回，上一层则拿着下一层返回的结果再创建一个结果，接着往上返回……这样的想法确实是因为把自己给绕进去了，官方的解法会更为直接明确。

看下提交的结果

提交的结果

虽然说这道题难度分为了中等，但是其实还算是比较简单的。

官方的解答比较详细，感兴趣的可以自行去查看。

推荐阅读更多精彩内容