牛客网新出了一个算法速刷 TOP101 题单，按照标签进行分类刷题，涵盖了链表、二分查找、排序、二叉树、堆、栈、队列、哈希、递归、回溯算法、动态规划、字符串、双指针、贪心算法、模拟算法等多个高频知识考点，准备校招、临时突击算法面试的同学可以根据这份题单进行系统的刷题。
题单地址：https://www.nowcoder.com/link/pc_kol_wsx
一、题目描述
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个结点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]
提示：
- 每个链表中的结点数在范围
[1, 100]内 0 <= Node.val <= 9- 题目数据保证列表表示的数字不含前导零
二、题目解析
对于这道题目来说，模拟一下整个过程就不难发现计算规律了，就和数学的加法逻辑是一样的，都需要处理进位的问题。
1、构建一个链表用来存放 l1 和 l2 两个链表相加的结果。
2、设置一个进位 carryBit，初始化为 0，用来计算和接收当前两个个位数相加的结果。
3、同时遍历 l1 和 l2，只要此时 l1 和 l2 两个链表中的任意一个链表中结点有值，就一直加下去，直到两个链表中的所有结点都遍历完毕为止。
4、获取 l1 链表中结点的值，如果当前结点为 null，那么用 0 来表示，否则用当前结点的值，记录为 x 。
5、获取 l2 链表中结点的值，如果当前结点为 null，那么用 0 来表示，否则用当前结点的值，记录为 y 。
6、计算 x + y + carryBit 的结果，取这个结果的个位数加入到结果链表中，取这个结果的十位数更新到 carryBit 上面。
7、跳出循环之后，如果 carryBit 为 1 ，那么需要再创建一个结点值为 1 的结点，连接到结果链表的后面。
8、最后返回虚拟头结点的下一个结点就是结果。
三、参考代码
// 本题文字版详解请访问下方网站
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 构建一个链表用来存放 l1 和 l2 两个链表相加的结果
// 其中 dummy 这个结点为虚拟头结点
ListNode dummy = new ListNode(-1);
// 设置一个进位，初始化为 0
// 两个个位数相加，进位只能是 1 或者 0
// 比如 7 + 8 = 15，进位是 1
// 比如 2 + 3 = 6，没有进位，或者说进位是 0
int carryBit = 0;
// l1 和 l2 有可能为空，所以先默认结果链表从虚拟头结点位置开始
ListNode cur = dummy;
// 同时遍历 l1 和 l2
// 只要此时 l1 和 l2 两个链表中的任意链表中结点有值，就一直加下去
// 直到两个链表中的所有结点都遍历完毕为止
while(l1 != null || l2 != null) {
// 获取 l1 链表中结点的值
int x;
// 观察此时 l1 中的结点是否有值
// 如果结点不存在，那么就用 0 来占位
if( l1 == null){
// 用 0 来占位
x = 0;
}else{
// 否则，将 l1 的结点值赋值给 x
x = l1.val;
}
// 获取 l2 链表中结点的值
int y;
// 观察此时 l2 中的结点是否有值
// 如果结点不存在，那么就用 0 来占位
if( l2 == null){
// 用 0 来占位
y = 0;
}else{
// 否则，将 l2 的结点值赋值给 y
y = l2.val;
}
// 每一位计算的同时需要考虑上一位的进位情况
int sum = x + y + carryBit;
// 获取当前计算结果的十位数
// 比如 7 + 8 = 15
// 那么 sum / 10 = 1，进位为 1
carryBit = sum / 10;
// 获取当前计算结果的个位数
// 比如 7 + 8 = 15
// 那么 sum % 10 = 5
int digit = sum % 10;
// 构建一个结点用来存放这个个位数
ListNode digitNode = new ListNode(digit);
// 把这个结点加入到结果链表中
cur.next = digitNode;
// 移动 cur 的位置，观察后面应该存放什么结点
cur = cur.next;
// l1 链表中还有结点未遍历完毕就继续遍历下去
if(l1 != null) l1 = l1.next;
// l2 链表中还有结点未遍历完毕就继续遍历下去
if(l2 != null) l2 = l2.next;
}
// 两个链表的尾结点相加之后，有可能产生进位的情况
// 所以，需要构建一个新的结点用来存放这个进位的结果
if(carryBit == 1) {
// 构建一个结点用来存放这个进位
ListNode carryBitNode = new ListNode(carryBit);
// 把这个结点加入到结果链表中
cur.next = carryBitNode;
}
// 最后返回结果链表的头结点就行，即虚拟头结点的下一个结点
return dummy.next;
}
}
