<>题目描述

我一开始的思路是:遍历这两个链表,将这两个数还原回去,然后做运算,将运算完的结果再按照要求逆序取出来,做成一个链表。实际上应该是可行的,

<>初次尝试

但是:


我还原回去的数用了一个int类型的变量来接收,但是当第1559个用例时,这个还原回去的数就已经超过了int类型了……迫于无奈,我将类型换成了long类型,我想着这下应该够了把,结果:

第1560个用例,直接来了这么长,好像有30位,long类型范围好像是在20位左右,头大,难道换成继续换成double类型的?要是他来个几百位怎么办?换思路换思路,而且是时候换成double好像也无法实现。
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) { double l1Num =
getNum(l1); double l2Num = getNum(l2); double sum = l1Num + l2Num; ListNode temp
= new ListNode((int) (sum%10)); ListNode re = temp; sum = Math.floor(sum/10);
while (sum > 0) { int each = (int) (sum % 10); System.out.println(each);
ListNode listNode= new ListNode(each); temp.next = listNode; temp = listNode;
sum= Math.floor(sum/10); } return re; } public static double getNum(ListNode l1)
{ double sum = 0; int count = 0; while (l1 != null) { int val = l1.val; sum +=
val*Math.pow(10,count); l1 = l1.next; count++; } System.out.println(sum); return
sum; }
<>更换思路

之前的思路被否决的之后,就思考:为什么要把这个两个数复原回去呢?复原回去之后还要重新遍历。那就不复原,直接遍历这两个链表,在遍历的过程中,将对应位置的数加起来。

这个思路是可行的,但是要考虑边界情况和进位情况,我按照这个思路,写出了初代版本,然后各种提交调试,最后通过了
boolean carry = false; //进位标志,注意要重置 ArrayList<Integer> l1ArrayList = new
ArrayList<>(); while (l1 != null) { l1ArrayList.add(l1.val); l1 = l1.next; } int
size1= l1ArrayList.size(); ArrayList<Integer> l2ArrayList = new ArrayList<>();
while (l2 != null) { l2ArrayList.add(l2.val); l2 = l2.next; } int size2 =
l2ArrayList.size(); int firstSum = l1ArrayList.get(0)+l2ArrayList.get(0);
ListNode temp= new ListNode(firstSum%10); ListNode re = temp; if (firstSum >=10)
{ carry = true; if (size1 ==1 && size2 == 1) { temp.next = new ListNode(firstSum
/10); } } for (int i = 1,j = 1; i<size1 || j<size2; i++,j++) { int num1 ; if (i
>= size1) { num1 = 0; } else { num1= l1ArrayList.get(i); } int num2 ; if (j >=
size2) { num2 = 0; } else { num2 = l2ArrayList.get(j); } int sum = num1 + num2;
ListNode eachTemp= new ListNode(sum%10); if (carry) { if (sum%10 +1 < 10) {
eachTemp= new ListNode(sum%10+1); carry = false; } else { eachTemp = new
ListNode(0); carry = true; } } temp.next = eachTemp; temp = eachTemp; if (sum >=
10) { carry = true; } } if (carry) { temp.next = new ListNode(1); } return re;
效果不是很理想

<>优化

我透,我是个傻逼啊,我为什么要先将两个链表遍历一遍放入集合中,再从集合中取?直接在遍历的时候去不就可以了??这不是脱了裤子放屁吗
boolean carry = false; //进位标志,注意要重置 int firstNum = l1.val + l2.val; ListNode
temp= new ListNode(firstNum%10); ListNode re = temp; l1 = l1.next; l2 = l2.next;
if (firstNum >= 10) { carry = true; if (l1 == null && l2 == null) { temp.next =
new ListNode(firstNum/10); } } while (l1 != null || l2 != null) { int num1; if (
l1== null) { num1 = 0; } else { num1 = l1.val; } int num2; if (l2 == null) {
num2= 0; } else { num2 = l2.val; } int sum = num1 + num2; ListNode eachTemp =
new ListNode(sum%10); if (carry) { if (sum % 10 < 9) { eachTemp = new ListNode(
sum%10+1); carry = false; } else { eachTemp = new ListNode(0); carry = true; } }
temp.next = eachTemp; temp = eachTemp; if (sum >= 10) { carry = true; } if (l1
!= null) { l1 = l1.next; } if (l2 != null) { l2 = l2.next; } } if (carry) { temp
.next = new ListNode(1); } return re;
省掉了两次遍历链表,提交结果

果然,效果明显的提升啊,估计我当时脑子抽了。我最开始好像想的是,因为题目将这个数逆置了,所以不能直接遍历,从尾部开始遍历,又因为单链表无法倒序遍历,所以才先正序遍历,存入了集合中。想多了想多了

<>大佬思路

官方给出的思路也是我上面那种思路,但是他细节方面除了的很好,代码量是我的四分之一,完成的功能却是一样的。细节主要有:

* 他用了一个哑节点,用来处理头结点和尾节点,而我是分别特殊处理的
*
他用了一个0和1的数值来处理进位问题,而我用的是一个布尔类型的标记。用数值类型,可以直接加上这个数值,而用布尔类型,需要判断,再决定加或不加,无形之中增加了工作量。
代码
ListNode dummyHead = new ListNode(0); ListNode p = l1, q = l2, curr =
dummyHead; int carry = 0; while (p != null || q != null) { int x = (p != null) ?
p.val : 0; int y = (q != null) ? q.val : 0; int sum = carry + x + y; carry =
sum/ 10; curr.next = new ListNode(sum % 10); curr = curr.next; if (p != null) p
= p.next; if (q != null) q = q.next; } if (carry > 0) { curr.next = new ListNode
(carry); } return dummyHead.next;
优秀!!!

技术
©2019-2020 Toolsou All rights reserved,
数字滚动抽奖小程序VaR - 风险价值 - 蒙特卡罗法 - Python百度网盘偷偷更新,终于实现免费不限速了! Chrome OS,对程序员和Windows意味着什么?,互联网营销华为Mate 40 Pro+ 5G曝光:徕卡电影镜头、陶瓷机身Qt学习2——.pro文件和.h文件介绍python:将一个文件转换为二进制文件(binary)第十一届蓝桥杯C/C++ 大学 B 组大赛软件类省赛网站手机号码抓取方式蚂蚁集团香港IPO获得中国证监会批准