阿亮的算法之路——2. 两数相加

题目描述

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

初次尝试

但是：

我还原回去的数用了一个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;

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

大佬思路

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

1. 他用了一个哑节点，用来处理头结点和尾节点，而我是分别特殊处理的
2. 他用了一个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;

优秀！！！