LeetCode刷题实战2：用链表模拟加法

亦凉 2022-12-02 04:20 100阅读 0赞

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！

废话不多说，让我们一起来看看题目吧，今天要讲的是一道经典的算法题，虽然不难，但是很有意思，我们一起来看下题目：

> You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
> 
> You may assume the two numbers do not contain any leading zero, except the number 0 itself.
> 
> https://leetcode.com/problems/two-sum/

**翻译**

给定两个非空的链表，代表两个非负整数。这两个整数都是倒叙存储，要求返回一个链表，表示这两个整数的和。

**样例**

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)  
Output: 7 -> 0 -> 8  
Explanation: 342 + 465 = 807.

**解答**

题目不难理解，思路也很容易想明白，其实就是模拟小学生打竖式计算加减的方法，来计算两个整数的加和。但是既然是加法，就可能涉及进位，比如两个两位数的和可能是一个三位数。还有一个难点是需要使用链表来实现，涉及链表，编码的复杂度会更大一些。

在开始编码之前，我们先仔细观察样例：

![image][]

如果你熟悉C++ STL或者其他语言工具库的用法，想必应该很容易想到可以使用map。map是一个非常常用的容器，用来存储key-value格式的数据对。我们发现，由于链表存储数字的顺序和常规的顺序相反，所以如果存在进位的情况，我们只需要在链表的结尾加上一个节点即可。通常的计算是从右往左，而在链表当中可以理解成从左往右，其实也就是按照链表遍历的顺序计算。这点想明白，并没有什么问题。我们做一个总结，难点大概有三个：1. 因为不是数组，所以我们无法拿到链表的长度。会出现两个链表长度不一致的情况2. 返回结果也是一个链表，需要我们自己手动创建3. 计算产生的进位处理我们一个一个来分析，链表的长度未知很好处理，我们只需要判断当前节点的next节点是否为空，就可以知道链表后面是否还有后继。如果没有，那么就说明链表已经遍历到头了。由于本题当中存在两个链表，我们需要同时判断它们是否结束：

while (l1 || l2) {
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }

手动创建链表也并不复杂，我们首先创建一个链表的节点，然后依次往节点后方插入节点即可。链表插入的方式也很简单，假设当前的节点是cur，待插入的节点是node，那么我们只需要用cur.next指向node，然后将cur赋值成node即可，如图：

![image][image 1]

cur->next = node;
    cur = node;

计算产生的进位问题就更简单了，由于我们是按位来计算加法，所以我们可以用一个变量标记之前位是否发生进位。如果发生，那么当前的计算结果加一。因为加法计算，最多的结果只能达到19（两位9再加上之前进位），所以进位最多只会增加1。最后，再判断一下当前位计算的结果是否产生进位即可。

int ret = l1->val + l2->val;
    if (exceed) ret++;
    if (ret > 9) {
        ret -= 10;
        exceed = true;
    }else exceed = false;

最后，我们只需要把上述说到的三点结合起来，就可以写出代码了。如果coding还是有困难，可以在公众号回复LeetCode2，获取代码。

还没有结束，在大多数语言当中，int都是有范围的。一般是32个二进制位，如果是int64则是64个二进制位。这是和计算机CPU的带宽是有关的，那有没有想过，超过64位二进制能表示的整数应该怎么办呢？

其实就是用类似本题当中的方法，通过链表将每一位串联起来，在计算加减乘除的时候，则是像人工打竖式那样去计算。这种算法称为**高精度**。感兴趣的同学，可以自行搜索，以后有机会，会在之后的文章里更新。

希望大家都能有所收获，如果喜欢本文，麻烦顺手转发或者点击下方“**在看**”。

**上期推文：**

[LeetCode刷题实战1：在数组上遍历出花样][LeetCode_1]

![image][image 2]

[image]: /images/20221123/c93005e409cc42b78228587db44c6946.png
[image 1]: /images/20221123/cfec4dfe353642988a3006851f29de20.png
[LeetCode_1]: http://mp.weixin.qq.com/s?__biz=MzA5NzgzODI5NA==&mid=2454046571&idx=4&sn=e3feaa51aa57d4896d23752e7ec8335d&chksm=872bd2d2b05c5bc40e94fc4398f1be4eb1a6721a259a01ec006106892f53ccab96328a209925&scene=21#wechat_redirect
[image 2]: /images/20221123/763e46ec745243479dbe5eb1314e422f.png