Loading... # [两数相加](https://leetcode-cn.com/problems/add-two-numbers/description/) | Category | Difficulty | Likes | Dislikes | | :-: | :-: | :-: | :-: | | algorithms | Medium (37.65%) | 4515 | - | 给出两个 **非空** 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 **逆序** 的方式存储的,并且它们的每个节点只能存储 **一位** 数字。 如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外,这两个数都不会以 0 开头。 **示例:** ``` 输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807 ``` --- [Discussion](https://leetcode-cn.com/problems/add-two-numbers/comments/) | [Solution](https://leetcode-cn.com/problems/add-two-numbers/solution/) ## 解法 ### 读题 实质上类似于小学学习的加法竖式,加了有进位就进到下一位 其实是为了考察单向链表的操作和理解 以及引用类型的理解 ### 解法 按照加法竖式的思想,链表遍历,计算当前位,有则进位,无则不进位 需要注意的是,两个数的长度可能不一样比如 100+12 ```c# /** * Definition for singly-linked list. * public class ListNode { * public int val; * public ListNode next; * public ListNode(int x) { val = x; } * } */ public class Solution { public ListNode AddTwoNumbers(ListNode l1, ListNode l2) { //结果链表 ListNode res = new ListNode(0); //前一个节点 var preNode = res; //进位 int val = 0; //有一个不为空,计算 while (l1 != null || l2 != null) { //当前和(没有进位前,有可能有一个是null,null时为0) val = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + val; //进位余数,当前与10取余 preNode.next =new ListNode(val % 10); //节点移动 preNode = preNode.next; //进位数,当前与10相除 val = val / 10; //节点移动 l1 = l1?.next; l2 = l2?.next; } //注意判断最后一次计算还有进位的情况,有的话赋值节点 if (val != 0) preNode.next = new ListNode(val); return res.next; } } ``` ### 思考 时间复杂度: O(max(m,n))【两个数中最大长度是多少就算多少次】 空间复杂度: O(max(m,n))【结果最多多一位 即max(m,n)+1】 可不可以转化为int计算后再转回去?可能是一种逻辑,但是似乎时间和空间复杂度都会在链表和int互转的时候有所提升。 【敲黑板知识点!】最后为什么返回一个res.next呢?兄弟萌想到了吧! <img src="https://traceless.tech/usr/themes/handsome/assets/img/emotion/aru/pouting.png" class="emotion-aru"> ### 膜拜大佬 如果大佬们有更好的解法,不如评论分享赐教~ [我的Leetcode解题代码库][1] [1]: https://github.com/traceless0929/.leetcode Last modification:July © Allow specification reprint Support Appreciate the author AliPayWeChat Like 0 如果觉得我的文章对你有用,请随意赞赏