链表求和
题目描述
给定两个用链表表示的整数,每个节点包含一个数位。
这些数位是反向存放的,也就是个位排在链表首部。
编写函数对这两个整数求和,并用链表形式返回结果。
输入:(7 -> 1 -> 6) + (5 -> 9 -> 2),即617 + 295
输出:2 -> 1 -> 9,即912
题解(java)
复制代码
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
34class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { //虚拟头节点(哑结点) ListNode dummy = new ListNode(0); ListNode temp = dummy; //进位 int carry = 0; while(l1!=null || l2!=null || carry>0){ int i = l1==null? 0 : l1.val; int j = l2==null? 0 : l2.val; //相加之和(包含进位的) int sum = i + j +carry; if(sum>=10){ //尾插法连接 temp.next = new ListNode(sum%10); }else{ temp.next = new ListNode(sum); } //更新进位的值 carry = sum / 10; temp = temp.next; if(l1!=null){ l1 = l1.next; } if(l2!=null){ l2 = l2.next; } } return dummy.next; } }
图示
详解(尾插法连接)
- 1>.简单来说,该题需要四个变量,一个是 l1 节点的值 i,一个是 l2 节点的值 j,一个是进位数 count,一个是计算总和的值,其中进位数初始化为0。
- 2>.当 i,j,count中只要有一个不为 null 或 0时,都需要进入遍历,产生新的节点用头插法连接到链表中去
- 3>.其中进位数 count = sum/10,新的节点的值分为两种情况:【1).当sum<10时,temp.next == sum,当 sum >= 10时,需要对sum进行取余,即temp.next == sum%10】
- 最后返回新的节点
进阶
进阶:思考一下,假设这些数位是正向存放的,又该如何解决呢?
示例:
输入:(6 -> 1 -> 7) + (2 -> 9 -> 5),即617 + 295
输出:9 -> 1 -> 2,即912
- 这里先把原来的两个链表反转,再采用头插法连接即可
声明
- 原作者:E.L.E
- <本文章著作权归作者所有,商业转载请获得作者授权,非商业转载请注明出处>
- <欢迎大家评论>
最后
以上就是年轻鱼最近收集整理的关于链表求和(尾插法)链表求和的全部内容,更多相关链表求和(尾插法)链表求和内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复