2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
例子
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]输出：[7,0,8]解释：342 + 465 = 807.示例 2：
输入：l1 = [0], l2 = [0]输出：[0]示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]输出：[8,9,9,9,0,0,0,1]提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9
题目数据保证列表表示的数字不含前导零
V1-简单思路
思路
l1 反转构建为数字
l2 反转构建为数字
num = l1+l2
然后反转列表输出。
坑：这里限定了入参是一个单向链表
java 实现
这里使用 BigInteger，因为位数会比较长，避免超长的情况。
importjava.math.BigInteger;importjava.util.LinkedList;importjava.util.List;importjava.util.ListIterator;/** * @author binbin.hou * @since 1.0.0 * @date 2020-6-9 11:38:48 */publicclassT002_AddTwoNumbers{publicstaticclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}/** * 最基本思路 * @param l1 列表1 * @param l2 列表2 * @date 2020-6-9 12:08:44 */publicListNodeaddTwoNumbers(ListNodel1,ListNodel2){List<Integer>numOneList=getIntegerList(l1);List<Integer>numTwoList=getIntegerList(l2);BigIntegernumOne=buildBigInteger(numOneList);BigIntegernumTwo=buildBigInteger(numTwoList);BigIntegersum=numOne.add(numTwo);returnbuildListNode(sum);}/** * 构建最后的结果 * @param sum 和 * @return 结果 * @since 1.0.0 */privateListNodebuildListNode(finalBigIntegersum){Stringstring=sum.toString();ListNodeheadNode=buildListNode(string,string.length()-1);ListNodecurrentNode=headNode;for(inti=string.length()-2;i>=0;i--){currentNode.next=buildListNode(string,i);currentNode=currentNode.next;}returnheadNode;}privateListNodebuildListNode(Stringstring,intindex){intinteger=Integer.parseInt(string.charAt(index)+"");returnnewListNode(integer);}/** * 获取整数的链表 * @param listNode 节点 * @return 结果 * @since 1.0.0 */publicList<Integer>getIntegerList(ListNodelistNode){// 使用 linkedList，避免扩容List<Integer>resultList=newLinkedList<>();ListNodeoneNode=listNode;while(oneNode!=null){intvalue=oneNode.val;resultList.add(value);oneNode=oneNode.next;}returnresultList;}/** * 根据单个数字构建 BigInteger，不知道入参有多长 * @param integers 数组 * @return 结果 * @since 1.0.0 */privateBigIntegerbuildBigInteger(finalList<Integer>integers){// 逆序遍历 LinkedList 应该有双向指针，理论上不慢。integers.iterator();ListIterator<Integer>iterator=integers.listIterator(integers.size());// 避免扩容StringBuilderstringBuilder=newStringBuilder(integers.size());while(iterator.hasPrevious()){intinteger=iterator.previous();stringBuilder.append(integer);}returnnewBigInteger(stringBuilder.toString());}}效果
这种是比较慢的。
Runtime: 18 ms, faster than 5.29% of Java online submissions for Add Two Numbers.Memory Usage: 40.4 MB, less than 16.38% of Java online submissions for Add Two Numbers.V2-记录进位
思路
每一个节点的值都是 0-9，处理的时候其实我们只需要关心相加是否进位即可。
并不需要这么复杂的把信息处理完相加，从而减少处理时间。
java 实现
说明：这里是自己实现模拟了 BigInteger 的加法。
importjava.util.LinkedList;importjava.util.List;/** * 官方的解法 * * 核心： * 5+7=12 会产生进位，但是最多只有一次进位 * 因为：9+9+1=19 * * @author binbin.hou * @since 1.0.0 * @date 2020-6-9 11:38:48 */publicclassT002_AddTwoNumbersV1{publicstaticclassListNode{intval;ListNodenext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}/** * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) * Output: 7 -> 0 -> 8 * Explanation: 342 + 465 = 807. * * 注意： * （1）两个列表并不是一样长的，可能还有数字为空。 * （2）末尾也可能产生进位 * * 思路： * 直接遍历链表，使用一个位置保留进位。 * * 列表的遍历一直是以最长的为准，走到最后。 * * @param l1 列表1 * @param l2 列表2 * @return 结果 * @date 2020-6-9 12:08:44 */publicListNodeaddTwoNumbers(ListNodel1,ListNodel2){List<Integer>oneList=getIntegerList(l1);List<Integer>twoList=getIntegerList(l2);//[5,5] 最后一位进1intsize=oneList.size()>twoList.size()?oneList.size():twoList.size();// 借助第三条数组，存放进位int[]overflowFlags=newint[size+1];// 直接构建结果列表ListNodeheadNode=buildListNode(oneList,twoList,0,overflowFlags);ListNodecurrentNode=headNode;for(inti=1;i<size;i++){currentNode.next=buildListNode(oneList,twoList,i,overflowFlags);currentNode=currentNode.next;}// 最后如果存在进位的话if(overflowFlags[size]==1){currentNode.next=newListNode(1);}returnheadNode;}/** * 构建元素列表 * * （1）为了避免 index == 0 时，判断 * 将 index==0 时的信息直接保存在 0 位，当前进位保存在下一位。 * @param oneList 第一个列表 * @param twoList 第二个列表 * @param index 下标 * @param overflowFlags 越界标识 * @return 结果 */privateListNodebuildListNode(finalList<Integer>oneList,finalList<Integer>twoList,finalintindex,int[]overflowFlags){intone=getIndexValue(oneList,index);inttwo=getIndexValue(twoList,index);intsum=one+two;intpreviousOverflow=overflowFlags[index];// 一般都是小于 10intvalue=sum+previousOverflow;if(value>=10){overflowFlags[index+1]=1;// 保留个位value-=10;}returnnewListNode(value);}/** * 获取下标对应的值 * @param list 列表 * @param index 下标 * @return 值 * @since 1.0.0 */privateintgetIndexValue(finalList<Integer>list,finalintindex){if(index<list.size()){returnlist.get(index);}return0;}/** * 获取整数的链表 * @param listNode 节点 * @return 结果 * @since 1.0.0 */privateList<Integer>getIntegerList(ListNodelistNode){// 使用 linkedList，避免扩容List<Integer>resultList=newLinkedList<>();ListNodeoneNode=listNode;while(oneNode!=null){intvalue=oneNode.val;resultList.add(value);oneNode=oneNode.next;}returnresultList;}}效果
效果如下：
Runtime: 3 ms, faster than 29.29% of Java online submissions for Add Two Numbers.Memory Usage: 42.64 MB, less than 47.4% of Java online submissions for Add Two Numbers.V3-优化链表遍历
思路
上面的方式中，对于链表的遍历是分别独立进行的。
性能至少有两个优化点：
1）同时遍历两个链表
2）遍历链表的同时，构建节点
内存优化：因为是一边遍历，一边构建节点。所以进位的标识，可以用一个值替代。
java 实现
importcom.github.houbb.leetcode.ListNode;/** * 官方的解法 * * 核心： * 5+7=12 会产生进位，但是最多只有一次进位 * 因为：9+9+1=19 * * 核心流程： * * @author binbin.hou * @since 1.0.0 * @date 2020-6-9 11:38:48 */publicclassT002_AddTwoNumbersV3{/** * 进位标识 * @since 0.0.1 */privatestaticvolatileintoverflowFlag=0;/** * Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) * Output: 7 -> 0 -> 8 * Explanation: 342 + 465 = 807. * * TODO: 要学会避免前两次的列表循环。 * * 注意： * （1）两个列表并不是一样长的，可能还有数字为空。 * （2）末尾也可能产生进位 * * 思路： * 直接遍历链表，使用一个位置保留进位。 * * 列表的遍历一直是以最长的为准，走到最后。 * * * @param l1 列表1 * @param l2 列表2 * @return 结果 * @date 2020-6-9 12:08:44 */publicListNodeaddTwoNumbers(ListNodel1,ListNodel2){overflowFlag=0;// 直接构建结果列表ListNodeheadNode=buildListNode(l1,l2);ListNodecurrentNode=headNode;ListNodel1Next=l1.next;ListNodel2Next=l2.next;while(l1Next!=null||l2Next!=null){currentNode.next=buildListNode(l1Next,l2Next);currentNode=currentNode.next;// 往后遍历if(l1Next!=null){l1Next=l1Next.next;}if(l2Next!=null){l2Next=l2Next.next;}}// 最后如果存在进位的话if(overflowFlag==1){currentNode.next=newListNode(1);}returnheadNode;}/** * 获取下一个元素值 * * 默认返回 0 * @param listNode 当前节点 * @return 下一个节点的值 * @since 1.0.0 */privateintgetValue(ListNodelistNode){if(listNode==null){return0;}returnlistNode.val;}/** * 构建元素列表 * * （1）为了避免 index == 0 时，判断 * 将 index==0 时的信息直接保存在 0 位，当前进位保存在下一位。 * @param l1 节点1 * @param l2 节点2 * @return 结果 * @since 0.0.1 */privateListNodebuildListNode(ListNodel1,ListNodel2){intvalueOne=getValue(l1);intvalueTwo=getValue(l2);intsum=valueOne+valueTwo+overflowFlag;if(sum>=10){sum-=10;overflowFlag=1;}else{overflowFlag=0;}returnnewListNode(sum);}}效果
效果如下：
Runtime: 1 ms, faster than 100.00% of Java online submissions for Add Two Numbers.Memory Usage: 39.7 MB, less than 44.45% of Java online submissions for Add Two Numbers.小结
对于链表的题目，基本都可以先使用笨方法，把节点放点列表中，然后处理，构建结果列表来解决。
但是这种性能基本是最差的。
对于节点的遍历和构建，值得我们进一步思考与学习。
开源地址
为了便于大家学习，所有实现均已开源。欢迎 fork + star~
参考资料
https://leetcode.cn/problems/add-two-numbers/
