【链表】力扣 2. 两数相加

一、题目

二、思路

• 当两个节点的 val 进行相加时有可能会产生进位，由于每个节点只能存储 一位 数字，因此，当进位产生时，只会向下一节点 进位1。
• 整个问题可以分解为：将对齐后的链表相应节点进行 val 相加，再加上由上一次产生的进位（初始进位设为 0）。这样便把原来较大的原问题，划分成了多个与原问题相似的规模更小的子问题。因此，可以采用 递归 来解决。

三、题解

/**
 * 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) {
        return addTwo(l1, l2, 0);
    }
    public ListNode addTwo(ListNode l1, ListNode l2, int carry) {
        // 递归出口：只有当两个链表的节点都为 null 时，才不用将这两个节点的 val 进行相加的操作
        //          但需要考虑上一位产生的进位问题
        if (l1 == null && l2 == null) {
            // 进位为 0 返回给上一级为 null，否则新创建一个值为 进位 的一个节点
            return carry == 0 ? null : new ListNode(carry);
        }
        // 不妨一直用 l1 来表示两个链表中较长的那个链表，最后 return l1
        if (l1 == null) {// 上面的递归出口已经排除了两个链表都为 null 的情况
            l1 = l2;
            l2 = null;
        }
        int sum = l1.val + (l2 == null ? 0 : l2.val) + carry;
        l1.val = sum % 10;
        carry = sum /10;
        l1.next = addTwo(l1.next, l2 == null ? null : l2.next, carry);
        return l1;
    }
}