2.两数相加
【摘要】
题目：
分析：
链表中所给的数中，都是按照逆序排序的，也就是说高位在后面，低位在前面，到时候两数相加涉及到低位向高位进位的问题，可以定义一个进位标识。
实现：
public class Two...
题目：
分析：
链表中所给的数中，都是按照逆序排序的，也就是说高位在后面，低位在前面，到时候两数相加涉及到低位向高位进位的问题，可以定义一个进位标识。
实现：
public class TwoNumAdd {
//解题主方法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = null, tail = null; //标记头尾，头部最后用来输出，尾部用来连接其他节点
int carry = 0; //进位标志，初始位0
while (l1 != null || l2 != null) { //两个节点中，只有还有节点不为空就继续
int x = l1 != null ? l1.val : 0; //因为while循环中，是||的判断，存在为空的情况，l1不为空的话x取l1的val值，为空x就取0
int y = l2 != null ? l2.val : 0; //同上
int addNum = x + y + carry; //计算相同位数节点的和（带有地位的进位标志）
carry = addNum / 10; //取进位标志
if (head == null) { //第一次head为空
tail = head = new ListNode(addNum % 10);
} else {
tail.next = new ListNode(addNum % 10); //之后用tail来添加新节点
tail = tail.next;
}
if (l1 != null) //如果l1不为空，就取l1的下一个节点
l1 = l1.next;
if (l2 != null) //同上
l2 = l2.next;
}
if (carry == 1) { //while循环结束后，判断是否最高位计算结果是否有进位，在两位数加法中进位只有1
tail.next = new ListNode(1);
tail = tail.next;
}
return head;
}
public static void main(String[] args) {
int []arr1 = new int[]{9,9,9,9,9,9,9};
int []arr2 = new int[]{9,9,9,9};
ListNode l1 = arrToListNode(arr1);
ListNode l2 = arrToListNode(arr2);
ListNode listNode = new TwoNumAdd().addTwoNumbers(l1, l2);
ArrayList<Integer> arr = new ArrayList<>();
listNodeToArr(listNode,arr);
System.out.println(arr);
}
//把数组封装成ListNode
public static ListNode arrToListNode(int []arr){
ListNode head = null,tail = null;
for (int i : arr) {
if(head == null){
head = tail = new ListNode(i);
}else {
tail.next = new ListNode(i);
tail = tail.next;
}
}
return head;
}
//递归把ListNode转换为数组
public static void listNodeToArr(ListNode listNode, ArrayList al){
if(listNode.next!=null){
al.add(listNode.val);
listNode = listNode.next;
listNodeToArr(listNode,al);
}
else{
al.add(listNode.val);
}
}
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
测试输出结果：
递归实现：
public class TwoNumAdd {
//解题主方法
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
int addNum = 0;
ListNode head = null, tail = null;
ListNode listNode = this.addTwoNumbersByRecursion(l1, l2, carry,addNum,head,tail);
return listNode;
}
public ListNode addTwoNumbersByRecursion(ListNode l1 ,ListNode l2 , int carry,int addNum,ListNode head,ListNode tail) {
if (l1 != null || l2 != null) {
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
addNum = x + y + carry;
carry = addNum / 10;
if (head == null) {
tail = head = new ListNode(addNum % 10);
} else {
tail.next = new ListNode(addNum % 10);
tail = tail.next;
}
if (l1 != null)
l1 = l1.next;
if (l2 != null)
l2 = l2.next;
head = addTwoNumbersByRecursion(l1, l2, carry, addNum, head, tail);
return head;
} else {
if (carry == 1) {
tail.next = new ListNode(1);
tail = tail.next;
}
return head;
}
}
public static void main(String[] args) {
int []arr1 = new int[]{9,9,9,9,9,9,9};
int []arr2 = new int[]{9,9,9,9};
ListNode l1 = arrToListNode(arr1);
ListNode l2 = arrToListNode(arr2);
ListNode listNode = new TwoNumAdd().addTwoNumbers(l1, l2);
ArrayList<Integer> arr = new ArrayList<>();
listNodeToArr(listNode,arr);
System.out.println(arr);
}
//把数组封装成ListNode
public static ListNode arrToListNode(int []arr){
ListNode head = null,tail = null;
for (int i : arr) {
if(head == null){
head = tail = new ListNode(i);
}else {
tail.next = new ListNode(i);
tail = tail.next;
}
}
return head;
}
//递归把ListNode转换为数组
public static void listNodeToArr(ListNode listNode, ArrayList al){
if(listNode.next!=null){
al.add(listNode.val);
listNode = listNode.next;
listNodeToArr(listNode,al);
}
else{
al.add(listNode.val);
}
}
}
class ListNode {
int val;
ListNode next;
public ListNode(int val) {
this.val = val;
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
文章来源: blog.csdn.net，作者：Mr.Yushiwen，版权归原作者所有，如需转载，请联系作者。
原文链接：blog.csdn.net/MrYushiwen/article/details/119885952
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）