LeetCode-两数相加（java递归）

在这里插入图片描述

这是力扣上的第二题：两数相加，也是刚开始接触力扣刷题，这道中等难度的算法题还是耗费了不少时间解出来，觉得还挺有意思，所以想把过程和自己的思路记录下来，废话不多说，直接上解题思路。

解题思路：

本题解法是递归实现。解题思路其实很简单，题目给的需求是两个链表相加，每个节点位置存放的数字和只能是0-9区间，那么就需要满10进1，进位值暂且用carry表示，由此得出： n1+n2+carry。
最直接的解题思路就是递归：每次当前两个节点相加，然后递归相加这两个节点的next节点，递归的终止条件就是直到两个链表都没有next节点时，返回结果就可以。

解题过程中，需要注意的三个点：
1、两个链表的长度有可能不一致，那么长度短的链表，就需要用0补齐到与另一个链表相等长度，避免出现相加过程中，因为长度不一致而导致出现空指针异常。
2、当两个链表相加到最后一个节点时，需要特殊校验是否满足进位条件，如果满足条件需要再附加一位保存carry，然后当前节点的值对10取余就可以了。
3、一定一定要确保递归的终止条件哟，不然你懂得。。。

代码实现：

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        // 计算两个节点数值和
        int val = l1.val + l2.val;
        // 计算进位值：两个节点相加是否大于10
        int carry = val / 10;
        // 是否满足递归终止条件：两个阶段都无next
        if (l1.next == null && l2.next == null) {
            // 已满足终止条件，但此时有两种情况，最后两个节点相加是否大于10，如果大于10需要进位，否则直接返回
            return val < 10 ? new ListNode(val) : new ListNode(val % 10, new ListNode(carry));
        }
        // 创建一个节点对象
        ListNode node = new ListNode(val);
        // 处理两个链表长度不一致情况，长度短的链表用carry进位值补齐
        if (l1.next == null) {
            l1.next = new ListNode(carry);
        } else if (l2.next == null) {
            l2.next = new ListNode(carry);
        } else {
            // 两个链表有还有next节点，将carry加到某一个节点上，加到哪个节点上都可以，这里是默认加到l1节点值上
            l1.next.val += carry;
        }
        // 每个节点只能保存0-9的数字，所以对10取余
        node.val %= 10;
        // 递归累加
        node.next = addTwoNumbers(l1.next, l2.next);
        return node;
    }