【透过算法了解编程】之两数相加

【透过算法了解编程】之两数相加

Hello，大家好，我是猿码叔叔，2022年的第一天就迫不及待的与大家见面了，开森 ~。

2022是一个偶数，且无论个位十位还是百位都是偶数，预示每一位阅读以及博主自己一定会脱单。

今天要写的是两数相加，比起去年的两数之和的难度稍稍有些提升，但不影响我们透过算法了解编程的乐趣。

题目： 两数相加（Add Two Numbers）

题目介绍：

给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

来源：力扣（LeetCode）

大家注意了，这道题给的是链表。关于链表大家有兴趣可以去了解我之前写的博文《链表真的那么难吗? 基础＋练习带你领略链表的奇妙之处》。 

题目分析：

在做这道题之前，我们需要去温习一下加法（Plus）的笔算过程。笔算过程一般有 3 个特点，我们可以使用算法模拟这 3 个特点以达到笔算效果，进而解开题目。

加法笔算的 3 大特点：

• 两个加数会向右对齐，并由右至左，也就是低位向高位进行同位计算

链表的每一个节点分别代表两个加数的高低位数字，题目中明确说明链表存储的是逆序数字，因此我们无需使用额外的  时间，去反转链表，使得链表中的数字进行高低位反转。

• 低位向高位进行同位计算，超出或等于 10，将保留超出 10 的部分，向高位进 1

这个很好解决，定义变量 ，

有节点   和 ，,  表示两个节点的值与前一位两个节点的值计算之和的余数之和取余 10 求得。

• 两个加数的位数不同或相同

这是这道题比较难处理的点之一，如果在不增加额外的空间复杂度的情况下，1 个循环是很难遍历两个不同长度的链表，因此我们需要增加额外的空间，

即当  为 null，而  不为 null 时我们需要为后者创建一个新的后继节点，以达到位数不同时，高位补 0 的效果。

 下面给个示例：

8 8 9               ——          0 8 8 9

1 2 3 4            ——          1 2 3 4

 代码实现

    public ListNode addTwonumbers(ListNode l1, ListNode l2) {
        // ans 保留原有链表的顺序；
        ListNode ans = l1, tmp = l1;
        // r 为两节点之和的超出 10 的余数
        int r = 0, sum;
        while (l1 != null && l2 != null) {
            // 求和
            sum = l1.val + l2.val + r;
            // 向前进 1 位
            r = sum > 9 ? 1 : 0;
            l1.val = sum % 10;
            // 判断是否需要高位补 0，也就是两个链表长度是否相等
            if(l1.next == null && l2.next != null) {
                l1.next = new ListNode(0);
            }
            // 与上面同理
            if(l1.next != null && l2.next == null) {
                l2.next = new ListNode(0);
            }
            // tmp 存储 l1 最后一个节点
            tmp = l1;
            // 遍历
            l1 = l1.next; l2 = l2.next;
        }
        // 两个加数最高位相加 >= 10 时，需要向前进 1
        if(r == 1) tmp.next = new ListNode(1);
        return ans;
    }

时间复杂度： ,  为  链表的长度， 为  链表的长度

空间复杂度：

代码分析：

• 变量：ans

链表经过遍历后不再是  节点，因此根据题目要求，我们需要保留原有的链表顺序，那么 变量就是起到这个作用。由于它引用了 变量，无论我们如何 *** 作 ，都只会改变 中的值，而不是顺序。

• 变量: tmp

变量是获取 或  节点的最后一个节点。如果我们以 节点存储两数之和，那么无论两个链表的长度是否相等，最终都会在长度最长的那个链表的最后一个节点结束遍历，意味着当两个数字的最高位之和大于或等于 10，我们需要在循环外去解决这个向高位进 1 的问题，那么此时 变量的作用就很明显了。 

下面画了张草图： 

• 判断是否需要高位补 0：

高位是否需要补 0，具有相对性，

当  为 null，且  不为 null 时

或

当  不为 null，且  为 null 时

• 两加数最高位是否需要进 1：

这个取决于局部变量 ， 每轮计算只有 2 个值，0 或 1，因此，当循环结束若  为 1，意味着最高位需要进 1，此时我们为  变量创建一个值为 1 的后继节点，由于它引用了 链表，同时  变量也引用了 节点，进而会影响它的值。

 总结 

算法，有时就是在模拟人类思想和行为的方式，或者说是作为人类行为和思想的若干个片段，而这些片段又可以组合起来成为一个庞大的中央处理器，那么不同的处理器又负责不同的运算功能移植在硬件当中，最后组成一个机器人。所以当我们学习算法时，其实就是在用编码进行人类思想和行为的再现。比如：逆波兰式运算、有效的括号、括号生成等类似的算法都是一些很好的代表。

学习点：

1. 如何使用程序模拟一件事情的执行过程
2. 链表如何在遍历中创建新节点
3. 如何获取链表的最后一个节点

 结语

2021年已去，2022年伊始。猿码在这里祝大家新年快乐，也希望大家能在 CSDN 这个平台如虎添翼，技术更上一层楼。