LeetCode 2.两数相加（单链表、高精度）

秒速五厘米 2023-02-18 11:56 8阅读 0赞

**上一篇博客：[LeetCode 1.两数之和（数组、哈希表）][LeetCode 1.]**

> 写在前面：大家好！我是`ACfun`,我的昵称来自两个单词`Accepted`和`fun`。我是一个热爱ACM的蒟蒻。最近萌生了刷LeetCode的想法，所以我打算从LeetCode简单的题目开始做起，攻陷LeetCode。如果博客中有不足或者的错误的地方欢迎在评论区或者私信我指正，感谢大家的不吝赐教。我的唯一博客更新地址是：[https://ac-fun.blog.csdn.net/][https_ac-fun.blog.csdn.net]。非常感谢大家的支持。一起加油，冲鸭！  
>  `用知识改变命运，用知识成就未来！加油 (ง •̀o•́)ง (ง •̀o•́)ง`

原题链接：[LeetCode 2. 两数相加][LeetCode 2.]

### 文章目录 ###

*  题目信息
 *   *  题目描述
     *  示例
 *  解题思路
 *  时间复杂度
 *  解题代码
 *  提交情况

# 题目信息 #

## 题目描述 ##

给出两个 **非空** 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 **逆序** 的方式存储的，并且它们的每个节点只能存储 **一位** 数字。  
 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。  
 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

## 示例 ##

> 输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)  
> 输出：7 -> 0 -> 8  
> 原因：342 + 465 = 807

# 解题思路 #

刚开始看题目的时候看到了需要使用链表感觉这个题目应该很难，其实这是个错觉。这个题目本质上就是我们平常做加法的方法，从个位开始加超过10就进位，然后依次将个位十位百位……相加最后得出结果。我们也可以通过数组来实现，但是题目有限制，让我们使用链表来做。  
 我觉得这还是一个高精度问题，高精度问题在之前的博客 [蓝桥杯练习系统 基础练习（vip试题）：BASIC-30 阶乘计算][_vip_BASIC-30] 中提到过。大家感兴趣可以去看一看，这里就不赘述了。  
 首先申请一个头结点，然后再申请一个结点sum，sum结点指向头结点。定义一个carry变量用来进位，初始化为0，然后就开始遍历 l1 和 l2 两个单链表，只要这两个单链表不为空或者carry不为0就进行相加操作。分别判断当前结点是否为空，如果不为空说明第一个数或者第二个数该数位上还有数值，那么就将其加到carry上。然后申请一个新的结点使其指向sum的下一个结点，数值为carry % 10，如果carry小于10那么carry还是原数值，如果carry大于10，那么就会只将个位保存在该结点上。然后使carry / 10，如果carry大于10那么只会保留十位上的数字，即完成了进位操作，不断进行这个操作，直到 l1 为空 l2 为空并且 carry 为 0。最后返回头结点的下一个结点，即结果链表的真正的地址。  
![两数相加][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]

# 时间复杂度 #

假设链表 l1 的长度为m，l2 的长度为n，max表示两者之间的最大值，则该方法的时间复杂度为：O(max(m,n))。

# 解题代码 #

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */
    class Solution { 
    public:
        ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { 
             //auto dummy = new ListNode(-1),sum = dummy; auto变量可以在声明变量的时候根据变量初始值的类型自动为此变量选择匹配的类型
             ListNode *head = new ListNode(),*sum = head;   //申请一个头结点head，并使sum指向head。
             int carry = 0; //carry 用来进位
             while(l1 || l2 || carry){ 
                 if(l1) carry += l1->val, l1 = l1->next;
                 if(l2) carry += l2->val, l2 = l2->next;
                 sum->next = new ListNode(carry % 10);
                 sum = sum->next;   //更新头结点
                 carry /= 10;
             }
             return head->next;
        }
    };

# 提交情况 #

![提交情况][20200617201249744.png]

--------------------

> 未完待续，持续更新中……  
> ![冲鸭][20200617202007156.png]

[LeetCode 1.]: https://ac-fun.blog.csdn.net/article/details/106757604
[https_ac-fun.blog.csdn.net]: https://ac-fun.blog.csdn.net/
[LeetCode 2.]: https://leetcode-cn.com/problems/add-two-numbers/
[_vip_BASIC-30]: https://ac-fun.blog.csdn.net/article/details/105792627
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200617201114933.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxNTc1NTA3,size_16,color_FFFFFF,t_70
[20200617201249744.png]: https://img-blog.csdnimg.cn/20200617201249744.png
[20200617202007156.png]: https://img-blog.csdnimg.cn/20200617202007156.png