第1.1篇·两数相加

算法是求职的敲门砖，大厂面试一面几乎都会问算法题，以此来考察候选人的思维逻辑及编码能力。

今天要AC的题目叫做「两数相加」，在 leetcode 上的原题链接为：https://leetcode-cn.com/problems/add-two-numbers/，这道题主要考察的是链表这种数据结构。

1. 题目

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

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

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

示例1：输入为 2->4->3 和 5->6->4，输出是 7->0->8。（342+465=708）

示例2：输入为 0 和 0，输出是 0。（0+0=0）

示例3：输入为 9->9->9->9->9->9->9 和 9->9->9->9，输出是 8->9->9->9->0->0->0->1。（9999999+999=89990001）

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

假设链表的数据结构是：

 public class ListNode {
     int val;
     ListNode next;
     ListNode() {}
     ListNode(int val) { this.val = val; }
     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}

2. 解题思路

先来说说题目大意：输入为两个链表，代表两个数字，输出为这两者之和，也用链表表示。需要注意的是，输入的链表是数字的倒叙，如输入2->4->3则代表数字342。同时，题目会保证输入的两个数字不会以0开头，也就是说链表的尾节点不会为0。

可能有些同学会考虑先把链表转化为 int 或 long 类型的数字，然后进行加法运算，最后再转化为链表输出，但是即便是 long 也是有最大值的（2^64 -1，也就是9223372036854775807），而链表的最大长度有100个节点，所以这种方法是不可取的，必定会导致溢出。

换一种思路，其实题目还是比较简单的，我们只需要对两个链表的每一位进行求和运算，然后处理进位的情况即可。大致就是：首先定义一个链表用来存储计算结果，然后声明一个变量用于进位，然后对两个链表进行循环，从第一个节点开始进行加法运算，将结果赋值给新创建的链表节点，然后将原始链表进行后移一位，直到循环结束。

用 Java 实现上述的思路就是：

上述示例代码在 leetcode 上的执行结果是：

最后，本文收录于个人语雀知识库: 我所理解的后端技术，欢迎来访。