LeetCode题解 #2 Add Two Numbers
题目大意:使用链表表示的两个整数,计算出其和,以同样的形式返回。
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
觉得做OJ最大的问题是有时看不懂题目。
其实是这样的,一个链表代表一个非负整数数,是从右往左看的:
(2 -> 4 -> 3) = 342;
(5 -> 6 -> 4)=465;
342+465=7 -> 0 -> 8=807;
逆序其实是很大很大的便利!!!!
因为最左边是个位,只要这样一个个加,在考虑进位就好了。而且个位数相加,进位只能是1.
如果左边是最高位就麻烦了,因为数都是从最低位开始加的,还要遍历到最右边什么的。
所以思路如下:
1、一个用来记录进位的变量
2、如果两个链表都非空,把结点得数取出来,相加,对10取余构造新结点,记录进位。list=list.next
3、如果任意一个链表空了,就直接以他的结点构造新结点。
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode temp1 = l1;
ListNode temp2 = l2;
int temp =temp1.val+temp2.val;
//System.out.println("first------->"+temp);
int jinwei = 0;
if(temp>=10){
temp%=10;
jinwei=1;
}
temp1=temp1.next;
temp2=temp2.next;
ListNode result = new ListNode(temp);
ListNode resulttemp = result;
while(temp1!=null&&temp2!=null){
//连个链表都有结点,则两节点相加
temp =temp1.val+temp2.val;
//如果前面有进位
if(jinwei==1){
temp++;
jinwei--;
}
//考虑进位
if(temp>=10){
temp%=10;
jinwei=1;
}
resulttemp.next = new ListNode(temp);
temp1=temp1.next;
temp2=temp2.next;
resulttemp=resulttemp.next;
}
while(temp1!=null){
if(jinwei==1){
int t1 = ++temp1.val;
jinwei--;
if(t1>=10){
t1%=10;
jinwei++;
}
resulttemp.next = new ListNode(t1);
}
else{
resulttemp.next = new ListNode(temp1.val);
}
resulttemp=resulttemp.next;
temp1=temp1.next;
}
while(temp2!=null){
if(jinwei==1){
int t2 = ++temp2.val;
jinwei--;
if(t2>=10){
t2%=10;
jinwei++;
}
resulttemp.next = new ListNode(t2);
}
else{
resulttemp.next = new ListNode(temp2.val);
}
resulttemp=resulttemp.next;
temp2=temp2.next;
}
if(temp1==null&&temp2==null&&jinwei==1)
resulttemp.next = new ListNode(1);
return result;
}
}
所以说,大数的构造就应该这样构造,虽然是一道加法题,但是加减乘除都能很好的支持。
一开始想的是,把数取出来,然后构造一个数,再相加,然后再构造链表就行。但这样是错误的!!!
因为传入的链表可能很长很长,用long都会溢出的超级大数!
而且,这个代码是直接在LeetCode上写的,其实也挺方便,毕竟我只用printf来调试。也就是没了代码补全而已,不过不用写main函数也好。
最新文章
- Composer根据Name显示与隐藏
- XML特殊符号
- HTML 在安卓手机端软键盘弹出顶起页面布局的解决办法
- HttpURlconntiuon获取网络数据
- STL源码分析《4》----Traits技术
- Codeforces Round #217 (Div. 2) c题
- Axis2与Web项目整合
- 自定义JsonResult处理JSON序列化DateTime类型数据(Ext4.2+ASP.NET MVC 4)
- 基于visual Studio2013解决算法导论之049活动选择问题
- 版本控制器:SVN
- delphi中nil、null、UnAssigned区别
- Java并发编程:volatile 关键字
- java中继承和组合的区别
- Bash里面如何返回绝对路径
- C++二分查找算法演示源码
- 通过java代码往mysql数据库中写入日期相关数据少13个小时
- 理解和使用ThreadLocal类
- js加入购物车抛物线动画
- Docker 安装tensorflow
- noip2017普及 兔纸游玩记