力扣02 两数相加

题目：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

示例：

2→ 4 →3

5 → 6 → 4

结果： 7 → 0 → 8

输入：L1 = [2,4,3]

​ L2 = [5,6,4]

输出：L = [7,0,8]

注：因为4+6=10个位是0十位是1所以要向前进1

解法一： 迭代法

解题思路：

定义一个变量为total用来存储两个数字相加的和，定义一个变量为next1用来存储total的十位上的数字也就是需要向前进的数字，可以先建立一个虚拟头结点，这个虚拟头结点指向真正的ListNode，这样ListNode 不需要单独处理，直接 while 循环即可。

代码：

/**
 * 根据力扣的题目要求，求两数之后并按要求返回。
 * 方法一：迭代法
 */
public class addTwoNumbers01 {
    //1.定义一个方法返回ListNode,方法参数为两个链表ListNode l1 l2
    public ListNode addTwoNumbers(ListNode l1,ListNode l2){
        //1.1定义一个int类型的total用来存储两个数字的和,定义一个next1用来存储 total/10 的值 就是要向前进的数
        int total = 0;
        int next1 = 0;
        //1.2定义一个链表 用来存储要返回的数字
        ListNode listNode = new ListNode();
        //1.3定义一个curNode用来标记当前节点
        ListNode curNode = listNode;

        //2.1先循环遍历l1与l2长度相等的情况
        while (l1 != null && l2 != null){
            //2.2将l1的节点的值加上l2节点的值再加上next1赋值给total
            total = l1.value + l2.value + next1;
            //2.3取出total个位上的数字赋值给当前节点的下一个节点
            curNode.next = new ListNode(total%10);
            //2.4取出total上的十位数就是要向前进的数
            next1 = total / 10;
            //2.5分别将l1 l2 与当前节点向前移一位
            l1 = l1.next;
            l2 = l2.next;
            curNode = curNode.next;
        }
        //3.1如果l1与l2长度不相等且l2先遍历完
        while (l1 != null){
            //3.2将l1的值加上next1赋值给total
            total = l1.value + next1;
            curNode.next = new ListNode(total % 10);
            next1 = total / 10;
            l1 = l1.next;
            curNode = curNode.next;
        }
        //4.1如果l2还没遍历完
        while (l2 != null) {
            total = l2.value + next1;
            curNode.next = new ListNode(total % 10);
            next1 = total / 10;
            l2 = l2.next;
            curNode = curNode.next;
        }
        //5.如果最后两个链表都遍历完之后还需要向前进位
        if (next1 != 0){
            curNode.next = new ListNode(next1);
        }
        return listNode.next;
    }
}

注：

/ : 整除的结果是两个数相除的整数部分不包括余数

% ：取余的结果是两个数相除的余数部分不包括整数部分

示例： 10 / 7 = 1；10 % 7 = 3

解法二：递归法

解题思路：

最重要的就是要保证两个链表的长度相等，如果不相等我们也要想办法把它们变成相等（添加零节点）。

示例：

L1: 1 → 3 → 5 → 7 → 8 → 9

L2: 2 → 8 → 6 → 4 → 5

L ：3 → 1 → 2 → 2 → 4

L2下一节点为空了补上零节点:

L2： 2 → 8 → 6 → 4 → 5 → 0

L ： 3 → 1 → 2 → 2 → 4 → 0

根据规则还需要向前进1而L1,L2下一节点都为空所以都需要增加一个零节点

L1 ：1 → 3 → 5 → 7 → 8 → 9 → 0

L2 ：2 → 8 → 6 → 4 → 5 → 0 → 0

L ： 3 → 1 → 2 → 2 → 4 → 0 → 1

代码：

/**
 * 使用递归法：每次保证两个链表的长度一样长，不一样的给补成一样长
 */
public class addTwoNumbers02 {
    //1.定义一个方法返回ListNode参数位ListNode l1,l2
    public ListNode addTwoNumbers(ListNode l1,ListNode l2){
        //2.定义两个int类型的变量分别存储两数之和以及需要向前进位的数
        int total = l1.value + l2.value;
        int next1 = total / 10;
        //2.1定义一个节点用来存放两数之和各位上的数字
        ListNode node = new ListNode(total % 10);
        //3.保证两个链表长度相等并且将next1的值与l1的值进行相加
        if(l1.next != null || l2.next != null || next1 != 0){
            //3.1如果l1或者l2下一个节点不为空就继续向前走但凡有一个为空就新建一个0节点连接在后面
            l1 = l1.next != null ? l1.next : new ListNode(0);
            l2 = l2.next != null ? l2.next : new ListNode(0);
            //3.2将next1的值与l1的值进行相加
            l1.value += next1;
            //3.3进行递归
            node.next = addTwoNumbers(l1, l2);
        }
        return node.next;
    }
}

注： next1的不再是加在total上而是与L1.value相加。