本文转载自微信公众号《程序新视界》，作者二师兄丑胖子。转载本文，请联系程序新视野公众号。前言一个小学加法问题在LeetCode上被标记为“中等”难度。有的人“流无本事的眼泪”，有的人“一餐操作如虎，一眼就打败5%……”。今天我们就来看看LeetCode的第二题“双数相加”。《两个数相加》先看题目描述，对应官方链接：https://leetcode-cn.com/problems/add-two-numbers给你两个非空链表，代表两个非负整数.它们的每一个数字都是倒序存储的，每个节点只能存储一个数字。请将两个数字相加并以相同的形式返回表示总和的链表。可以假设除了数字0以外，其他数字都不以0开头。双数加法链表节点的数据结构如下：publicclassListNode{intval;ListNodeext;ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}标题描述标题描述比较绕。我们可以直接理解为两个多位整数相加，但是整数的每一位都是通过链表存储的。比如整数342，用链表存储正常应该是3->4->2，但是在计算的时候，往往需要从低位开始，而且每个小数都是1，所以题目直接表达了整数为2->4->3，所以不用颠倒链表的顺序，直接相加即可。两个数相加时需要注意，如果两个链表的长度不同，可以认为短链表后面有几个0。链表遍历结束后，如果进位值大于0，则需要在结果链表中添加一个值为1的结点。方法一：模拟上面说过，链表在倒序，所以你可以直接添加相应的数字。基本操作是遍历两个列表，逐位计算它们的和，并从当前位置开始添加进位值。比如两个链表对应的数分别是n1和n2，进位是进位（一般是0和1），那么它们的和就是（n1+n2+进位），对应的数就变成了（n1+n2+carry)%10，新进位为(n1+n2+carry)/10。如果两个链表的长度不一样，则长度最短的链表后续对应位的值全为0。如果遍历后carray大于0（即等于1),在结构链表后面增加一个新节点，实现代码如下：classSolution{publicListNodeaddTwoNumbers(ListNode1,ListNode2){ListNodehead=null,tail=null;intcarry=0;while(l1!=null||l2!=null){intn1=l1!=null?l1.val:0;intn2=l2!=null?l2.val:0;intsum=n1+n2+进位;if(head==null){head=tail=newListNode(sum%10);}else{tail.next=newListNode(sum%10);tail=tail.next;}carry=sum/10;if(l1!=null){l1=l1.next;}if(l2!=null){l2=l2.next;}}if(carry>0){tail.next=newListNode(carry);}returnhead;}??}上面的方法就是time-complex度的计算与链表的长度有关。比如两个链表的长度分别为m和n，那么遍历次数为max(m,n)，从m和n中取最大值，所以时间复杂度为O(n)。由于链表的每一位都需要计算和存储，如果最后有进位，就多加一位，所以最长链表为max(m,n)+1，所以空间复杂度为在）;通过idea分析和编写上面的代码还是比较容易的。但是这个问题可以递归解决吗？我们来看看方法二。方法二：递归第一种方法很简单，按照正常的思维逻辑即可。但是评论区有这么一句话，“没有递归就没有灵魂，虽然很多时候递归不一定更高效”。那我们就来看看递归的形式是如何实现的。classSolution{publicListNodeaddTwoNumbers(ListNode1,ListNode2){returnadd(l1,l2,0);}publicListNodeadd(ListNode1,ListNode2,intcarry){if(l1==null&&l2==null&&carry==0)returnnull;intx=l1==null?0:l1.val;inty=l2==null?0:l2.val;intsum=x+y+carry;ListNode=newListNode(sum%10);n.next=add(l1==null?null:l1.next,l2==null?null:l2.next,sum/10);returnn;}}上面代码的基本迭代逻辑循环如下：两个数相加通过上图可以推导出时间复杂度的递归调用。递归调用的时间复杂度计算本质上取决于：递归的次数？？每次递归中的操作数。那么，上述方法递归了多少次呢？递归的次数也和两个链表中最长的一个的长度有关。最后可能因为进位多计算了一次，所以递归次数为n或n+1，内部计算不是随机的。n变化，执行次数不变。所以整体的时间复杂度是n*1=O(n)。空间复杂度还是和结果链表的长度有关，所以还是O(n)。总结就算法本身而言，通过理清思路，逐步加入判断，得到解决方案。重点是大家能不能想出一个递归算法来回答。这道题的递归算法并没有降低时间复杂度，但是在某些情况下，递归算法可以将时间复杂度从O(n)降低到O(logn)，这将是一个很大的性能提升。比如求x的n次方，可以试试。
