力扣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相加。