力扣02 两数相加题目:

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

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

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

示例:

243

564

结果: 708

输入: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相加。