“两数相加”，小学加法运算而已，不用递归没有灵魂！

本文转载自微信公众号「程序新视界」，作者丑胖侠二师兄 。转载本文请联系程序新视界众号。  

10余年的湘潭县网站建设经验，针对设计、前端、开发、售后、文案、推广等六对一服务，响应快，48小时及时工作处理。成都全网营销推广的优势是能够根据用户设备显示端的尺寸不同，自动调整湘潭县建站的显示方式，使网站能够适用不同显示终端，在浏览器中调整网站的宽度，无论在任何一种浏览器上浏览网站，都能展现优雅布局与设计，从而大程度地提升浏览体验。创新互联建站从事“湘潭县网站设计”,“湘潭县网站推广”以来，每个客户项目都认真落实执行。

 前言

一道小学加法题，竟然在LeetCode上被标记为“中等”难度，有些人“流下了没有技术的眼泪”，有些人“一顿操作猛如虎，一看击败百分五……”。今天我们来看看LeetCode的第二道题“两数相加”。

“两数相加”

先来看题目描述，对应官方链接：https://leetcode-cn.com/problems/add-two-numbers

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字0之外，这两个数都不会以0开头。

两数相加

链表节点的数据结构如下：

 
 
 
 
    
  
  
  
  
  1. public class ListNode { 
    2. 
  
  
  
  
  2.    int val; 
    3. 
  
  
  
  
  3.    ListNode next; 
    4. 
  
  
  
  
  4.    ListNode() {} 
    5. 
  
  
  
  
  5.    ListNode(int val) { this.val = val; } 
    6. 
  
  
  
  
  6.    ListNode(int val, ListNode next) { this.val = val; this.next = next; } 
    7. 
  
  
  
  
  7.  } 
    8.

题目说明

题目描述相对来说比较绕，我们可以直接理解为两个多位的整数相加，只不过整数的每一位都是通过链表进行存储。比如，整数342，通过链表存储正常来说应该是3->4->2，但是计算时，往往需要从低位开始计算，逢十进一，所以题目中直接将整数表示为2->4->3，这样反而不用将链表顺序进行反转了，直接相加就可以了。

两数相加

需要注意的是如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 ，链表遍历结束，则如果进位值大于0，则还需要在结果链表中附加一个值为1的节点。

方法一：模拟

上面已经提到，链表是逆序的，因此直接对应数字相加即可。基本操作遍历两个列表，逐位计算它们的和，并与当前位置的进位值相加。

比如，两个链表对应位的数字分别为n1和n2，进位为carry(通常为0和1)，则它们的和为(n1 + n2 + carry)，对应位上数字变为(n1 + n2 + carry)%10，新的进位为(n1 + n2 + carry)/10。

如果两个链表长度不一样，长度短的链表后续对应位上值均为0即可。如果遍历结束之后，carray大于0(也就是等于1)，则在结构链表后面新增一个节点，

实现代码如下：

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
    3. 
  
  
  
  
  3.         ListNode head = null, tail = null; 
    4. 
  
  
  
  
  4.         int carry = 0; 
    5. 
  
  
  
  
  5.         while (l1 != null || l2 != null) { 
    6. 
  
  
  
  
  6.             int n1 = l1 != null ? l1.val : 0; 
    7. 
  
  
  
  
  7.             int n2 = l2 != null ? l2.val : 0; 
    8. 
  
  
  
  
  8.             int sum = n1 + n2 + carry; 
    9. 
  
  
  
  
  9.             if (head == null) { 
    10. 
  
  
  
  
  10.                 head = tail = new ListNode(sum % 10); 
    11. 
  
  
  
  
  11.             } else { 
    12. 
  
  
  
  
  12.                 tail.next = new ListNode(sum % 10); 
    13. 
  
  
  
  
  13.                 tail = tail.next; 
    14. 
  
  
  
  
  14.             } 
    15. 
  
  
  
  
  15.             carry = sum / 10; 
    16. 
  
  
  
  
  16.             if (l1 != null) { 
    17. 
  
  
  
  
  17.                 l1 = l1.next; 
    18. 
  
  
  
  
  18.             } 
    19. 
  
  
  
  
  19.             if (l2 != null) { 
    20. 
  
  
  
  
  20.                 l2 = l2.next; 
    21. 
  
  
  
  
  21.             } 
    22. 
  
  
  
  
  22.         } 
    23. 
  
  
  
  
  23.         if (carry > 0) { 
    24. 
  
  
  
  
  24.             tail.next = new ListNode(carry); 
    25. 
  
  
  
  
  25.         } 
    26. 
  
  
  
  
  26.         return head; 
    27. 
  
  
  
  
  27.     } 
    28. 
  
  
  
  
  28. } 
    29.

上述方法时间复杂度的计算与链表的长度有关，比如两个链表的长度分别为m和n，则遍历的次数为max(m,n)，也就m和n中取最大值，所以时间复杂度为O(n)。

由于要对链表的每一位进行计算存储，并且最后如果有进位，还要多加一位，因此最长链表为max(m,n)+1，所以空间复杂度为O(n);

通过思路分析，写出上面的代码还是比较容易的。但这个题目是否可以考虑用递归的形式来解决呢?我们来看看方法二。

方法二：递归

第一种方法很简单，按照正常的思维逻辑来就可以了。但评论区有这样一句话“不用递归没有灵魂。尽管多数时候，递归不见得更有效率。”那么我们就来看看用递归的形式如何实现。

 
 
 
 
    
  
  
  
  
  1. class Solution { 
    2. 
  
  
  
  
  2.     public ListNode addTwoNumbers(ListNode l1, ListNode l2) { 
    3. 
  
  
  
  
  3.         return add(l1,l2,0); 
    4. 
  
  
  
  
  4.     } 
    5. 
  
  
  
  
  5.     public ListNode add(ListNode l1, ListNode l2, int carry){ 
    6. 
  
  
  
  
  6.         if(l1 == null && l2 == null && carry == 0) return null; 
    7. 
  
  
  
  
  7.         int x = l1==null ? 0 : l1.val; 
    8. 
  
  
  
  
  8.         int y = l2==null ? 0 : l2.val; 
    9. 
  
  
  
  
  9.         int sum = x + y + carry; 
    10. 
  
  
  
  
  10.         ListNode n = new ListNode(sum % 10); 
    11. 
  
  
  
  
  11.         n.next = add(l1==null ? null : l1.next, 
    12. 
  
  
  
  
  12.                      l2==null ? null : l2.next, 
    13. 
  
  
  
  
  13.                      sum/10); 
    14. 
  
  
  
  
  14.         return n;  
    15. 
  
  
  
  
  15.     } 
    16. 
  
  
  
  
  16. } 
    17.

上述代码的基本迭代逻辑循环如下：

两数相加

通过上图我们可以推演一下递归调用的时间复杂度。针对递归调用的时间复杂度计算，本质上要看：递归的次数??每次递归中的操作次数。那么，上述方法递归了几次呢?递归的次数也是与两个链表最长的那个的长度有关，最后可能会因为进位多算一次，因此递归次数为n或n+1，而内部计算并不随n的变化而变化，执行次数为常数。因此整体时间复杂度为n*1 = O(n)。

空间复杂度依旧与结果链表的长度有关，因此依旧为O(n)。

小结

就算法本身而言是比较简单的，理清思路，逐渐添加判断即可获得解法。重点在于大家是否能够想到通过递归算法来进行解答。本道题递归算法并没有让时间复杂度降低，而在某些情况下通过递归算法能将时间复杂度从O(n)降低到O(logn)，这将是很大性能提升。比如，求x的n次方，大家可以尝试一下。

分享文章：“两数相加”，小学加法运算而已，不用递归没有灵魂！
本文链接：http://www.shufengxianlan.com/qtweb/news10/510760.html

网站建设、网络推广公司-创新互联，是专注品牌与效果的网站制作，网络营销seo公司；服务项目有等

广告

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源： 创新互联

猜你还喜欢下面的内容

python知识

分类信息网站

成都展柜定制　　 　响应式建站　　 　成都服务器托管　　 　成都封阳台　　 　申请域名　　 　成都网站建设　　 　腾讯云香港空间　　 　卖链接　　 　广汉锦华建材　　 　成都微信二次开发　　 　移动服务器托管　　 　成都画册设计　　 　成都移动服务器托管　　 　画册设计制作　　 　成都网站改版　　 　手机网站版本　　 　成都网站推广　　 　定制网站　　 　香港云虚拟主机　　 　网页设计制作