002.两数相加

作者：沉默王二发布时间：2023-12-10T16:38:07.419+0800

之前星球还没有 Markdown 的功能，所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：

增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

并且增加了技术派专栏的阅读地址，只需要绑定星球编号就可以通过「微信扫码登录」的方式在技术派网站上阅读，这样大家的阅读选择也会更加多样化（语雀、技术派、星球都可以，喜欢哪个用哪个）。

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
技术派专栏地址：https://paicoding.com/column/7/ 2
星球原地址：https://t.zsxq.com/15BG6sYgX

我知道，市面上已经有不少的刷题笔记了，二哥也看过很多，但讲真，有些还是看不太懂，可能是因为天赋不够，也可能是因为这些刷题笔记一开始是针对 C语言、Python、Go 或者 C++ 的，后来才翻译成 Java 语言，就导致阅读起来并不幸福🥰。

那我希望《二哥的 LeetCode 刷题笔记》能够给学习算法的球友提供一些不一样的刷题思路，从我自己的角度出发，题解可能会更容易掌握，当然了，最重要的还是教给大家举一反三的解题能力。

这对于那些打算冲中大厂的球友来说，至关重要，因为中大厂几乎都会有算法的笔试题，然后才会有面试机会。当然了，对于那些想通过刷题来学习 Java 的球友，无疑也会多一种选择，冲。

在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！

题意

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

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

示例

输入：l1=[2,4,3],l2=[5,6,4]

解释：342+465=807

l1 存储的是 2、4、3，也就是整数 342，逆序嘛；
l2 存储的是 5、6、4，也就是整数 465，逆序嘛；
个位相加为 7（2+5），十位相加为 10（4+6，需要进位），百位相加为 7（3+4），加上进位的 1 就是 8

难度

中等

分析

首先，搞清楚“逆序”是什么。

逆序：从后往前的顺序，比如 123 的逆序是 321。

题目中的示例其实也给出了解释，假如逆序链表 l1 为 [2,4,3]，l2 为 [5,6,4]，那么 l1 代表的数字就是 342，l2 为 456。

对于还没有学过链表的球友来说，可以通过二哥的 Java 进阶之路中的**LinkedList **来学习一下链表的数据结构，大体上就这样：a->b->c->d

两数相加，如果不需要进位的话，就是把对应位置的数字相加，比如 342 + 456 = 798，非常简单。

难点就在于，进位该如何处理。

回想一下我们小学曾经学过的加法竖式，如下图。

对于每一位上的数字相加，都有可能产生进位，比如 4 + 6 = 10，那么 1 就是进位，我们需要把它加到下一位的和中即可。

假设两个链表相同位置的数字分别是 addX 和 addY，进位是 up，那么它们的和（sum）就是 addX + addY + up，如果 sum 大于 10 的话，需要进位，那么进位的值就是 sum / 10，而 sum % 10 就是当前位置的数字。

比如说个位 7+8=15（此时进位为 0），由于和大于 10，所以十位的进位就是 1（sum / 10），个位的数字就是 5（sum % 10）。

十位 4+6+1=11（此时进位为 1），由于和大于 10，所以百位的进位就是 1（sum / 10），十位的数字就是 1（sum % 10）。

百位 3+5+1=9（此时进位为 1），由于和小于 10，所以千位的进位就是 0（sum / 10），百位的数字就是 9（sum % 10）。

也就是说 347（对应的逆序链表为「7、4、3」）+568（对应的逆序链表为「8、6、5」）=915（新的逆序链表为 5、1、9），这就是我们最终的结果。

7+8=15，进位为 1，个位为 5；
4+6+1=11，进位为 1，十位为 1；
3+5+1=9，进位为 0，百位为 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; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); // 创建一个哨兵节点，方便返回结果 ListNode p = l1, q = l2, curr = dummyHead; // 初始化三个指针：p 和 q 分别遍历两个输入链表，curr 用于构建结果链表 int carry = 0; // 初始化进位值为 0 // 遍历两个链表直到全部结束 while (p != null || q != null) { // 获取当前节点的值，如果节点不存在则为 0 int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; // 计算两个值和进位值的总和 int sum = carry + x + y; // 更新进位值 carry = sum / 10; // 创建新节点，值为总和的个位数，并将其加入到结果链表 curr.next = new ListNode(sum % 10); // 移动 curr 指针到新节点 curr = curr.next; // 如果存在，移动 p 和 q 到各自链表的下一个节点 if (p != null) p = p.next; if (q != null) q = q.next; } // 循环结束后，如果仍有进位，则在结果链表末尾添加一个节点 if (carry > 0) { curr.next = new ListNode(carry); } // 返回哨兵节点的下一个节点，即结果链表的头节点 return dummyHead.next; }}

当输入是 l1 = [2,4,3] 和 l2 = [5,6,4] 时，我们来模拟一下整个题解过程：

初始化：创建一个哨兵节点 dummyHead 用于简化边界情况的处理，以及一个临时节点 curr 指向它。设置进位 carry 为 0。
开始遍历两个链表：
第一轮迭代：
l1 的当前元素是 2，l2 的当前元素是 5。
计算和：sum = 2 + 5 + 0 = 7（当前进位 carry 是 0）。
创建新节点，值为 sum % 10 = 7，进位 carry = sum / 10 = 0。
移动 curr 到新节点。
移动 l1 和 l2 分别到下一个节点。
第二轮迭代：
l1 的当前元素是 4，l2 的当前元素是 6。
计算和：sum = 4 + 6 + 0 = 10（当前进位 carry 是 0）。
创建新节点，值为 sum % 10 = 0，进位 carry = sum / 10 = 1。
移动 curr 到新节点。
移动 l1 和 l2 分别到下一个节点。
第三轮迭代：
l1 的当前元素是 3，l2 的当前元素是 4。
计算和：sum = 3 + 4 + 1 = 8（当前进位 carry 是 1）。
创建新节点，值为 sum % 10 = 8，进位 carry = sum / 10 = 0。
移动 curr 到新节点。
l1 和 l2 都没有下一个节点，结束遍历。
检查最后的进位：
检查 carry 是否大于 0。此处 carry = 0，所以不需要添加新节点。
返回结果：
返回 dummyHead.next ，即哨兵节点后的链表。结果为 7 -> 0 -> 8。

342+465=807，我们得到了正确的答案。

时间复杂度：

空间复杂度：

我擦嘞，竟然打败了 100% 的用户！

总结

本题其实是一个铺垫，就比如说给你了一个非常非常大的数，用 int、long 根本无法装下，那其实就可以把这个数简化为一个链表，每个节点存储一个数位，这样子就可以无限扩展了。

其实这道题的内核就是大数相加，只不过我们把大数用链表来表示了，并且题目限制了每个链表中的节点数在范围 [1, 100] 内。

其实计算机中的大多数思想都是这样的，当一个问题超复杂时，我们就简化它，把它拆分成一个个小问题，然后再去解决。

关于 while 循环和链表的知识，我这里补充一下学习资料。

力扣链接：https://leetcode.cn/problems/add-two-numbers/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

该题解目前只针对**二哥编程星球 **的球友开放，如果你也想一起打卡学习算法的话，扫下面的优惠券加入我们吧，星球目前 4000+ 人，定价 149 元，从当初的 99 元一路涨上来的，所以早就是优势，别再犹豫了。

（优惠券仅 300 张，数量有限）

一个人可以走得很快，但一群人才能走得更远。如果想去面中大厂的话，LeetCode 几乎是必刷的，二哥的 LeetCode 题解通俗易懂、图文并茂，理解给你举一反三的解题能力，冲鸭。

加餐

其实到这里，我们已经完美地解决了这道题目，但这里给大家拓展一下。

学过 Java 语法的球友应该知道，int数据类型的存储范围是-2^32到2^32-1，用来表示0-9的数也太大材小用了。

关于Java 的数据类型，二哥的 Java 进阶之路上有详细讲过，可以戳**链接🔗 **来进一步了解。

那要不用short或者char数据类型来表示，它们占用的内存空间比 int 要小很多。

除此之外，我们还可以直接利用int的**数位 **性质来解决这道题。

数位：把一个数字按照个、十、百、千等等一位一位地拆开，关注它每一位上的数字。如果拆的是十进制数，那么每一位数字都是 0~9，其他进制可类比十进制。

这时候就涉及到 压位高精 的知识了。

原本的高精度一开始是一个位置存储一个数位，但是int有足足9位，是能够完整显示0-9的，所以我们可以利用一个int来存储9位的数字，这样就大大节省了空间。

这里贴一个用C++实现的压位高精的大整数类，和 Java 中的 BigInteger 类似，可以用来存储和操作大数，这些数值超出了标准整数类型（如 int 或 long long int）的范围。并提供了基本的算术运算，包括加法、减法、乘法和除法，以及比较运算。

#define register

class BigNum {private: ll a[N]; int l;public: BigNum() { memset(a,0,sizeof a),l=1; } void init() { for(reg int i=1; i<=l; i++)a[i]=0; l=1; } void show() { printf("%lld",a[l]); for(reg int i=l-1; i; i--)printf("%013lld",a[i]); } void operator = (const reg ll &x) { init(); l=0; reg ll y=x; while(y)a[++l]=y%base,y/=base; } void rd() { init(); char s[NWEISHU]; reg char x=getchar(); reg int len=0; while(x>'9'||x<'0')x=getchar(); while(x>='0'&&x<='9') s[++len]=x,x=getchar(); reg int A=len/WEISHU,B=len%WEISHU; l=A+(B>0); for(reg int i=1; i<=A; i++)for(int j=1; j<=WEISHU; j++)a[i]=(a[i]<<1)+(a[i]<<3)+(s[len-iWEISHU+j]^'0'); for(reg int j=1; j<=B; j++)a[A+1]=(a[A+1]<<1)+(a[A+1]<<3)+(s[j]^'0'); } bool operator < (const BigNum &x) { if(l!=x.l)return l<x.l; for(reg int i=l; i; i--)if(x.a[i]!=a[i])return a[i]<x.a[i]; return false; } bool operator == (const BigNum &x) { if(l!=x.l)return false; for(reg int i=1; i<=l; i++)if(x.a[i]!=a[i])return false; return true; } bool operator > (const BigNum &x) { if(l!=x.l)return l>x.l; for(reg int i=l; i; i--)if(x.a[i]!=a[i])return a[i]>x.a[i]; return false; } bool operator <= (const BigNum &x) { if(l>x.l)return false; for(reg int i=l; i; i--)if(a[i]>x.a[i])return false; return true; } bool operator >= (const BigNum &x) { if(l<x.l)return false; for(reg int i=l; i; i--)if(a[i]<x.a[i])return false; return true; } BigNum operator + (const ll &x) { BigNum r; r.l=l; memcpy(r.a,a,sizeof a); r.a[1]+=x; for(reg int i=1; i<=r.l; i++)if(r.a[i]>=base) { r.a[i]-=base; if(i==r.l) { r.a[i+1]=1,r.l++; break; } else r.a[i+1]++; } return r; } BigNum operator + (const BigNum &x) { BigNum r; r.l=max(l,x.l); for(reg int i=1; i<=r.l; i++) { r.a[i]=0; if(i<=l)r.a[i]+=a[i]; if(i<=x.l)r.a[i]+=x.a[i]; } for(reg int i=1; i<=r.l; i++)if(r.a[i]>=base) { r.a[i]-=base; if(i==r.l) { r.a[i+1]=1,r.l++; break; } else r.a[i+1]++; } return r; } void operator += (const ll &x) { a[1]+=x; for(reg int i=1; i<=l; i++)if(a[i]>=base) { a[i]-=base; if(i==l) { a[i+1]=1,l++; break; } else a[i+1]++; } } void operator += (const BigNum &x) { l=max(l,x.l); for(reg int i=1; i<=x.l; i++)a[i]+=x.a[i]; for(reg int i=1; i<=l; i++)if(a[i]>=base) { a[i]-=base; if(i==l) { a[i+1]=1,l++; break; } else a[i+1]++; } } void operator -= (const ll &x) { a[1]-=x; reg int i=1; while(a[i]<0&&i<=l)a[i]+=base,a[i+1]--; if(a[l]==0)l--; } void operator -= (const BigNum &x) { for(reg int i=1; i<=x.l; i++)a[i]-=x.a[i]; for(reg int i=1; i<l; i++)if(a[i]<0) { a[i]+=base; if(i==l-1) { if(--a[i+1]==0)l--; break; } else a[i+1]--; } } BigNum operator - (const ll &x) { Big r; r.l=l,memcpy(r.a,a,sizeof a); r.a[1]-=x; for(reg int i=1; i<r.l; i++)if(r.a[i]<0) { r.a[i]+=base; if(i==r.l-1) { if(--r.a[i+1]==0)r.l--; break; } else r.a[i+1]--; } return r; } BigNum operator - (const BigNum &x) { Big r; r.l=max(l,x.l); for(reg int i=1; i<=r.l; i++) { r.a[i]=0; if(i<=l)r.a[i]+=a[i]; if(i<=x.l)r.a[i]-=x.a[i]; } for(reg int i=1; i<r.l; i++)if(r.a[i]<0) { r.a[i]+=base; if(i==l-1) { if(--r.a[i+1]==0)r.l--; break; } else r.a[i+1]--; } return r; } void operator = (const ll &x) { a[l+1]=0; for(reg int i=1; i<=l; i++)a[i]=x; for(reg int i=1; i<=l; i++)a[i+1]+=a[i]/base,a[i]%=base; if(a[l+1])l++; } BigNum operator * (const ll &x) { Big r; r.l=l; memcpy(r.a,a,sizeof a); for(reg int i=1; i<=r.l; i++)r.a[i]=x; for(reg int i=1; i<=l; i++)r.a[i+1]+=r.a[i]/base,r.a[i]%=base; if(r.a[l+1])r.l++; return r; } BigNum operator /= (const ll &x){ for(reg int i=l;i>=2;i--)a[i-1]+=a[i]%xbase,a[i]/=x; a[1]/=x; if(!a[l])l--; } BigNum operator / (const ll &x){ BigNum r; memcpy(r.a,a,sizeof a); r.l=l; for(reg int i=r.l;i>=2;i--)r.a[i-1]+=r.a[i]%x*base,r.a[i]/=x; r.a[1]/=x; if(!r.a[l])r.l--; return r; }};

代码很长，我这里给大家一个简版的，带有注释的，方便感兴趣的球友去进一步挖掘。

#define register

class BigNum {private: ll a[N]; // 存储大数的数组，每个元素代表大数的一部分 int l; // 数组 a 中有效元素的数量，即大数的长度 public: // 构造函数：初始化大数为 0 BigNum() { memset(a, 0, sizeof a), l = 1; } // 初始化函数：将大数重置为 0 void init() { for (reg int i = 1; i <= l; i++) a[i] = 0; l = 1; } // 显示函数：打印大数 void show() { printf("%lld", a[l]); for (reg int i = l - 1; i; i--) printf("%013lld", a[i]); } // 赋值操作符：从长整型赋值给大数 void operator = (const reg ll &x) { init(); l = 0; reg ll y = x; while (y) a[++l] = y % base, y /= base; } // 读入函数：从输入读入一个大数 void rd() { // 略去读入逻辑... } // 比较操作符：<, ==, >, <=, >= // 用于比较两个大数的大小 // 略去具体实现... // 加法操作符：实现大数与长整型的相加 BigNum operator + (const ll &x) { // 略去加法逻辑... } // 加法操作符：实现两个大数的相加 BigNum operator + (const BigNum &x) { // 略去加法逻辑... } // 加法赋值操作符：实现大数与长整型的相加赋值 void operator += (const ll &x) { // 略去加法赋值逻辑... } // 加法赋值操作符：实现两个大数的相加赋值 void operator += (const BigNum &x) { // 略去加法赋值逻辑... } // 减法、乘法和除法操作符 // 实现大数与长整型或另一个大数的相减、相乘和相除 // 略去具体实现...};

感兴趣的球友其实可以看一下 BigInteger 的源码。

之前星球还没有 Markdown 的功能，所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：

增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
技术派专栏地址：https://paicoding.com/column/7/ 2
星球原地址：https://t.zsxq.com/15BG6sYgX

在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！

题意

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

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

示例

输入：l1=[2,4,3],l2=[5,6,4]

解释：342+465=807

l1 存储的是 2、4、3，也就是整数 342，逆序嘛；
l2 存储的是 5、6、4，也就是整数 465，逆序嘛；
个位相加为 7（2+5），十位相加为 10（4+6，需要进位），百位相加为 7（3+4），加上进位的 1 就是 8

难度

中等

分析

首先，搞清楚“逆序”是什么。

逆序：从后往前的顺序，比如 123 的逆序是 321。

题目中的示例其实也给出了解释，假如逆序链表 l1 为 [2,4,3]，l2 为 [5,6,4]，那么 l1 代表的数字就是 342，l2 为 456。

对于还没有学过链表的球友来说，可以通过二哥的 Java 进阶之路中的**LinkedList **来学习一下链表的数据结构，大体上就这样：a->b->c->d

两数相加，如果不需要进位的话，就是把对应位置的数字相加，比如 342 + 456 = 798，非常简单。

难点就在于，进位该如何处理。

回想一下我们小学曾经学过的加法竖式，如下图。

对于每一位上的数字相加，都有可能产生进位，比如 4 + 6 = 10，那么 1 就是进位，我们需要把它加到下一位的和中即可。

比如说个位 7+8=15（此时进位为 0），由于和大于 10，所以十位的进位就是 1（sum / 10），个位的数字就是 5（sum % 10）。

十位 4+6+1=11（此时进位为 1），由于和大于 10，所以百位的进位就是 1（sum / 10），十位的数字就是 1（sum % 10）。

百位 3+5+1=9（此时进位为 1），由于和小于 10，所以千位的进位就是 0（sum / 10），百位的数字就是 9（sum % 10）。

也就是说 347（对应的逆序链表为「7、4、3」）+568（对应的逆序链表为「8、6、5」）=915（新的逆序链表为 5、1、9），这就是我们最终的结果。

7+8=15，进位为 1，个位为 5；
4+6+1=11，进位为 1，十位为 1；
3+5+1=9，进位为 0，百位为 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; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); // 创建一个哨兵节点，方便返回结果 ListNode p = l1, q = l2, curr = dummyHead; // 初始化三个指针：p 和 q 分别遍历两个输入链表，curr 用于构建结果链表 int carry = 0; // 初始化进位值为 0 // 遍历两个链表直到全部结束 while (p != null || q != null) { // 获取当前节点的值，如果节点不存在则为 0 int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; // 计算两个值和进位值的总和 int sum = carry + x + y; // 更新进位值 carry = sum / 10; // 创建新节点，值为总和的个位数，并将其加入到结果链表 curr.next = new ListNode(sum % 10); // 移动 curr 指针到新节点 curr = curr.next; // 如果存在，移动 p 和 q 到各自链表的下一个节点 if (p != null) p = p.next; if (q != null) q = q.next; } // 循环结束后，如果仍有进位，则在结果链表末尾添加一个节点 if (carry > 0) { curr.next = new ListNode(carry); } // 返回哨兵节点的下一个节点，即结果链表的头节点 return dummyHead.next; }}

当输入是 l1 = [2,4,3] 和 l2 = [5,6,4] 时，我们来模拟一下整个题解过程：

初始化：创建一个哨兵节点 dummyHead 用于简化边界情况的处理，以及一个临时节点 curr 指向它。设置进位 carry 为 0。
开始遍历两个链表：
第一轮迭代：
l1 的当前元素是 2，l2 的当前元素是 5。
计算和：sum = 2 + 5 + 0 = 7（当前进位 carry 是 0）。
创建新节点，值为 sum % 10 = 7，进位 carry = sum / 10 = 0。
移动 curr 到新节点。
移动 l1 和 l2 分别到下一个节点。
第二轮迭代：
l1 的当前元素是 4，l2 的当前元素是 6。
计算和：sum = 4 + 6 + 0 = 10（当前进位 carry 是 0）。
创建新节点，值为 sum % 10 = 0，进位 carry = sum / 10 = 1。
移动 curr 到新节点。
移动 l1 和 l2 分别到下一个节点。
第三轮迭代：
l1 的当前元素是 3，l2 的当前元素是 4。
计算和：sum = 3 + 4 + 1 = 8（当前进位 carry 是 1）。
创建新节点，值为 sum % 10 = 8，进位 carry = sum / 10 = 0。
移动 curr 到新节点。
l1 和 l2 都没有下一个节点，结束遍历。
检查最后的进位：
检查 carry 是否大于 0。此处 carry = 0，所以不需要添加新节点。
返回结果：
返回 dummyHead.next ，即哨兵节点后的链表。结果为 7 -> 0 -> 8。

342+465=807，我们得到了正确的答案。

时间复杂度：

空间复杂度：

我擦嘞，竟然打败了 100% 的用户！

总结

其实这道题的内核就是大数相加，只不过我们把大数用链表来表示了，并且题目限制了每个链表中的节点数在范围 [1, 100] 内。

其实计算机中的大多数思想都是这样的，当一个问题超复杂时，我们就简化它，把它拆分成一个个小问题，然后再去解决。

关于 while 循环和链表的知识，我这里补充一下学习资料。

力扣链接：https://leetcode.cn/problems/add-two-numbers/

一步一个脚印

（优惠券仅 300 张，数量有限）

加餐

其实到这里，我们已经完美地解决了这道题目，但这里给大家拓展一下。

学过 Java 语法的球友应该知道，int数据类型的存储范围是-2^32到2^32-1，用来表示0-9的数也太大材小用了。

关于Java 的数据类型，二哥的 Java 进阶之路上有详细讲过，可以戳**链接🔗 **来进一步了解。

那要不用short或者char数据类型来表示，它们占用的内存空间比 int 要小很多。

除此之外，我们还可以直接利用int的**数位 **性质来解决这道题。

这时候就涉及到 压位高精 的知识了。

#define register

代码很长，我这里给大家一个简版的，带有注释的，方便感兴趣的球友去进一步挖掘。

#define register

感兴趣的球友其实可以看一下 BigInteger 的源码。

之前星球还没有 Markdown 的功能，所以第一次发布的格式在星球里阅读的话很不友好，于是二哥打算重新优化一版《二哥的 LeetCode 刷题笔记》：

增加代码注释，这样大家更容易看懂并掌握题解；
增加参考资料，这样大家可以从零基础直接开刷，减轻新手刷题的阻力；
增加手绘图，这样大家更容易理解解题思路；
增加 ACM 输入输出，这样大家可以在 Intellij IDEA 中进行调试；
增加题解模拟，这样大家可以根据题解模拟整个题解过程，看完会有一种“哦哦”恍然大悟的感觉；
图片上传至 OSS 并配合 CDN，提升大家在技术派网站中的阅读体感。
另外，这一版本会作为 PDF 的终稿随后在星球进行发布。

语雀专栏地址+密码可通过星球置顶帖查看：https://t.zsxq.com/15rEo9Pdu
技术派专栏地址：https://paicoding.com/column/7/ 2
星球原地址：https://t.zsxq.com/15BG6sYgX

在这里，必须要感谢球友 @炳源，是我们的通力配合，才有了球友们看到的这份市面上独一无二的 LeetCode 刷题笔记。好，就让我们开始吧！

题意

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

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

示例

输入：l1=[2,4,3],l2=[5,6,4]

解释：342+465=807

l1 存储的是 2、4、3，也就是整数 342，逆序嘛；
l2 存储的是 5、6、4，也就是整数 465，逆序嘛；
个位相加为 7（2+5），十位相加为 10（4+6，需要进位），百位相加为 7（3+4），加上进位的 1 就是 8

难度

中等

分析

首先，搞清楚“逆序”是什么。

逆序：从后往前的顺序，比如 123 的逆序是 321。

题目中的示例其实也给出了解释，假如逆序链表 l1 为 [2,4,3]，l2 为 [5,6,4]，那么 l1 代表的数字就是 342，l2 为 456。

对于还没有学过链表的球友来说，可以通过二哥的 Java 进阶之路中的**LinkedList **来学习一下链表的数据结构，大体上就这样：a->b->c->d

两数相加，如果不需要进位的话，就是把对应位置的数字相加，比如 342 + 456 = 798，非常简单。

难点就在于，进位该如何处理。

回想一下我们小学曾经学过的加法竖式，如下图。

对于每一位上的数字相加，都有可能产生进位，比如 4 + 6 = 10，那么 1 就是进位，我们需要把它加到下一位的和中即可。

比如说个位 7+8=15（此时进位为 0），由于和大于 10，所以十位的进位就是 1（sum / 10），个位的数字就是 5（sum % 10）。

十位 4+6+1=11（此时进位为 1），由于和大于 10，所以百位的进位就是 1（sum / 10），十位的数字就是 1（sum % 10）。

百位 3+5+1=9（此时进位为 1），由于和小于 10，所以千位的进位就是 0（sum / 10），百位的数字就是 9（sum % 10）。

也就是说 347（对应的逆序链表为「7、4、3」）+568（对应的逆序链表为「8、6、5」）=915（新的逆序链表为 5、1、9），这就是我们最终的结果。

7+8=15，进位为 1，个位为 5；
4+6+1=11，进位为 1，十位为 1；
3+5+1=9，进位为 0，百位为 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; } * } */class Solution { public ListNode addTwoNumbers(ListNode l1, ListNode l2) { ListNode dummyHead = new ListNode(0); // 创建一个哨兵节点，方便返回结果 ListNode p = l1, q = l2, curr = dummyHead; // 初始化三个指针：p 和 q 分别遍历两个输入链表，curr 用于构建结果链表 int carry = 0; // 初始化进位值为 0 // 遍历两个链表直到全部结束 while (p != null || q != null) { // 获取当前节点的值，如果节点不存在则为 0 int x = (p != null) ? p.val : 0; int y = (q != null) ? q.val : 0; // 计算两个值和进位值的总和 int sum = carry + x + y; // 更新进位值 carry = sum / 10; // 创建新节点，值为总和的个位数，并将其加入到结果链表 curr.next = new ListNode(sum % 10); // 移动 curr 指针到新节点 curr = curr.next; // 如果存在，移动 p 和 q 到各自链表的下一个节点 if (p != null) p = p.next; if (q != null) q = q.next; } // 循环结束后，如果仍有进位，则在结果链表末尾添加一个节点 if (carry > 0) { curr.next = new ListNode(carry); } // 返回哨兵节点的下一个节点，即结果链表的头节点 return dummyHead.next; }}

当输入是 l1 = [2,4,3] 和 l2 = [5,6,4] 时，我们来模拟一下整个题解过程：

初始化：创建一个哨兵节点 dummyHead 用于简化边界情况的处理，以及一个临时节点 curr 指向它。设置进位 carry 为 0。
开始遍历两个链表：
第一轮迭代：
l1 的当前元素是 2，l2 的当前元素是 5。
计算和：sum = 2 + 5 + 0 = 7（当前进位 carry 是 0）。
创建新节点，值为 sum % 10 = 7，进位 carry = sum / 10 = 0。
移动 curr 到新节点。
移动 l1 和 l2 分别到下一个节点。
第二轮迭代：
l1 的当前元素是 4，l2 的当前元素是 6。
计算和：sum = 4 + 6 + 0 = 10（当前进位 carry 是 0）。
创建新节点，值为 sum % 10 = 0，进位 carry = sum / 10 = 1。
移动 curr 到新节点。
移动 l1 和 l2 分别到下一个节点。
第三轮迭代：
l1 的当前元素是 3，l2 的当前元素是 4。
计算和：sum = 3 + 4 + 1 = 8（当前进位 carry 是 1）。
创建新节点，值为 sum % 10 = 8，进位 carry = sum / 10 = 0。
移动 curr 到新节点。
l1 和 l2 都没有下一个节点，结束遍历。
检查最后的进位：
检查 carry 是否大于 0。此处 carry = 0，所以不需要添加新节点。
返回结果：
返回 dummyHead.next ，即哨兵节点后的链表。结果为 7 -> 0 -> 8。

342+465=807，我们得到了正确的答案。

时间复杂度：

空间复杂度：

我擦嘞，竟然打败了 100% 的用户！

总结

其实这道题的内核就是大数相加，只不过我们把大数用链表来表示了，并且题目限制了每个链表中的节点数在范围 [1, 100] 内。

其实计算机中的大多数思想都是这样的，当一个问题超复杂时，我们就简化它，把它拆分成一个个小问题，然后再去解决。

关于 while 循环和链表的知识，我这里补充一下学习资料。

力扣链接：https://leetcode.cn/problems/add-two-numbers/

一步一个脚印

（优惠券仅 300 张，数量有限）

加餐

其实到这里，我们已经完美地解决了这道题目，但这里给大家拓展一下。

学过 Java 语法的球友应该知道，int数据类型的存储范围是-2^32到2^32-1，用来表示0-9的数也太大材小用了。

关于Java 的数据类型，二哥的 Java 进阶之路上有详细讲过，可以戳**链接🔗 **来进一步了解。

那要不用short或者char数据类型来表示，它们占用的内存空间比 int 要小很多。

除此之外，我们还可以直接利用int的**数位 **性质来解决这道题。

这时候就涉及到 压位高精 的知识了。

#define register

代码很长，我这里给大家一个简版的，带有注释的，方便感兴趣的球友去进一步挖掘。

#define register

感兴趣的球友其实可以看一下 BigInteger 的源码。

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412