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