LeetCode高频题2：两数相加
提示：本题是系列LeetCode的150道高频题，你未来遇到的互联网大厂的笔试和面试考题，基本都是从这上面改编而来的题目
互联网大厂们在公司养了一大批ACM竞赛的大佬们，吃完饭就是设计考题，然后去考应聘人员，你要做的就是学基础树结构与算法，然后打通任督二脉，以应对波云诡谲的大厂笔试面试题！
你要是不扎实学习数据结构与算法，好好动手手撕代码，锻炼解题能力，你可能会在笔试面试过程中，连题目都看不懂！比如华为，字节啥的，足够让你读不懂题
题目
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照
逆序
的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
来源：力扣（LeetCode）
链接：
https://leetcode.cn/problems/add-two-numbers
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
一、审题
示例：
输入：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]
转数字加法是不行的！
加法嘛，
自然就是带进位的加法
从个位开始加，有进位带着走
首先你得了解计算机中存的数字的类型
int 32位长度的二进制，最大就2的32次方那么大，你数字的范围超过了这个范围
就没法表示了，问题就在这
如果你把链表直接转数字，加了之后，再转链表返回，一定会失败的，因为数字太大那种，没法加！
笔试AC解：遍历链表放数组，然后带进位加法，加就完事，空间复杂度o(n)
遍历俩表，找俩数组放起来
比如a数组，b数组分别放链表head1和head2
手撕代码很简单，耗费额外空间
但是大厂绝不会给你出这么简单的题目…………
就是繁琐，但是思想很简单，中间要注意结果ans需要多准备一个位置，最后最高位的进位如果是1，那还需要多增1位，否则进位是0不管了，也不需要生成链表
//复习笔试AC解，转数组，带进位相加
public static ListNode addTwoNumbersReview(ListNode l1, ListNode l2){
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;
int N1 = 0;
int N2 = 0;
ListNode cur = l1;
while (cur != null){
N1++;//统计N1长度
cur = cur.next;
}
cur = l2;
while (cur != null){
N2++;//统计N2长度
cur = cur.next;
}
//遍历俩链表，放入数组
int[] a = new int[N1];
int[] b = new int[N2];
cur = l1;
int index = 0;
while (cur != null){
a[index++] = cur.val;//转移
cur = cur.next;
}
cur = l2;
index = 0;
while (cur != null){
b[index++] = cur.val;//转移
cur = cur.next;
}
//可以玩加法了
int c = 0;//进位
index = 0;
int N = Math.max(N1, N2) + 1;//最大就是结果--多备份一个位置，万一是进位多出来了呢
int[] ans = new int[N];//结果
for (; index < N1 && index < N2; index++) {
//最多不会超短的长度
int tmp = a[index] + b[index] + c;//带进位加法
c = tmp/10;//把最高位拿下来11/10=1,进位，11%10模取余是1,这个是加法之后的非进位数
ans[index] = tmp % 10;
}
//把剩余的转移到ans中，把最高位那个进位带上
for (; index < N - 1; index++) {//多备份那个位置不管
//转移余下的数--看是谁长，加谁，a长转移a的，b长转移b的
int tmp = (N1 >= N2 ? a[index] : b[index]) + c;//带进位加法
c = tmp/10;//把最高位拿下来11/10=1,进位，11%10模取余是1,这个是加法之后的非进位数
ans[index] = tmp % 10;
}
//注意，可能最后还有一个c=1呢，要加上,c是0jiusuanl
ans[N - 1] = c != 0 ? c : 0;
//然后把数组整为链表
ListNode head = new ListNode(ans[0]);//头
cur = head;
for (int i = 1; i < N; i++) {
if (i == N -1 && ans[i] == 0) break;//最后那个位置是0就算了
ListNode newNode = new ListNode(ans[i]);
cur.next = newNode;
cur = cur.next;
}
return head;//挺复杂度哇
}
测试
自己再线下测试：
public static void test(){
ListNode l1 = new ListNode(9);
ListNode l2 = new ListNode(9);
ListNode l3 = new ListNode(9);
l1.next = l2;
l2.next = l3;
ListNode l4 = new ListNode(9);
ListNode l5 = new ListNode(9);
ListNode l6 = new ListNode(9);
ListNode l7 = new ListNode(9);
ListNode l8 = new ListNode(9);
ListNode l9 = new ListNode(9);
ListNode l10 = new ListNode(9);
ListNode l11 = new ListNode(9);
ListNode l12 = new ListNode(9);
ListNode l13 = new ListNode(9);
l4.next = l5;
l5.next = l6;
l6.next = l7;
l7.next = l8;
l8.next = l9;
l9.next = l10;
// l10.next = l11;
// l11.next = l12;
// l12.next = l13;
ListNode cur = l1;
while (cur != null){
System.out.print(cur.val +" ");
cur = cur.next;
}
System.out.println();
cur = l4;
while (cur != null){
System.out.print(cur.val +" ");
cur = cur.next;
}
System.out.println();
Solution solution = new Solution();
ListNode res = solution.addTwoNumbers2(l1, l4);
ListNode ans2 = solution.addTwoNumbersReview(l1, l4);
while (res != null) {
System.out.print(res.val +" ");
res = res.next;
}
System.out.println();
while (ans2 != null) {
System.out.print(ans2.val +" ");
ans2 = ans2.next;
}
}
public static void main(String[] args) {
test();
}
问题不大：
9 9 9
9 9 9 9 9 9 9
8 9 9 0 0 0 0 1
8 9 9 0 0 0 0 1
面试最优解，空间复杂度o(1)，直接在链表上完成加法
面试官考的绝对不是笔试AC解，它希望你，
能尽可能优化时间复杂度，就优化，本题，必然o(n)时间复杂度绕不开的
那么面试官肯定希望你优化空间复杂度，直接在链表上操作，考的就是你的这点能力，
因此，你需要直接生成链表来加，把进位带着，不要转数组了，而且转数组的代码其实也挺繁冗的，最后还要转数组啥的，麻烦死了
咱们带着链表的进位走一波
有进位，带着往前走
如果最后一位也有进位，也需要不断往下带
手撕代码注意链表的细节即可
//复习面试优化解，转数组，带进位相加
public static ListNode addTwoNumbersReview2(ListNode l1, ListNode l2) {
if (l1 == null && l2 == null) return null;
if (l1 == null) return l2;
if (l2 == null) return l1;
int c = 0;//进位
ListNode cur1 = l1;
ListNode cur2 = l2;
int tmp = cur1.val + cur2.val;
c = tmp/10;//进位
int val = tmp % 10;//去进位之后的和
cur1 = cur1.next;
cur2 = cur2.next;
ListNode ans = new ListNode(val);//至少是这个结果
ListNode cur = ans;
while (cur1 != null && cur2 != null){
//按照短的加
tmp = cur1.val + cur2.val + c;//带进位
c = tmp/10;//进位
val = tmp % 10;//去进位之后的和
ListNode newNode = new ListNode(val);
cur.next = newNode;//挂接到ans上
cur = cur.next;
cur1 = cur1.next;
cur2 = cur2.next;
}
cur1 = cur1 != null ? cur1 : cur2;//把长的给cur1吧，然后剩下的也给ans
while (cur1 != null){
//剩下的转移
tmp = cur1.val + c;//带进位
c = tmp/10;//进位
val = tmp % 10;//去进位之后的和
ListNode newNode = new ListNode(val);
cur.next = newNode;//挂接到ans上
cur = cur.next;
cur1 = cur1.next;
}
//最后看c的情况
if (c != 0){
ListNode newNode = new ListNode(c);
cur.next = newNode;//挂接到ans上
}
return ans;
}
不过为啥内存还降低了呢？
自己测试一把：
public static void test(){
ListNode l1 = new ListNode(9);
ListNode l2 = new ListNode(9);
ListNode l3 = new ListNode(9);
l1.next = l2;
l2.next = l3;
ListNode l4 = new ListNode(9);
ListNode l5 = new ListNode(9);
ListNode l6 = new ListNode(9);
ListNode l7 = new ListNode(9);
ListNode l8 = new ListNode(9);
ListNode l9 = new ListNode(9);
ListNode l10 = new ListNode(9);
ListNode l11 = new ListNode(9);
ListNode l12 = new ListNode(9);
ListNode l13 = new ListNode(9);
l4.next = l5;
l5.next = l6;
l6.next = l7;
l7.next = l8;
l8.next = l9;
l9.next = l10;
// l10.next = l11;
// l11.next = l12;
// l12.next = l13;
ListNode cur = l1;
while (cur != null){
System.out.print(cur.val +" ");
cur = cur.next;
}
System.out.println();
cur = l4;
while (cur != null){
System.out.print(cur.val +" ");
cur = cur.next;
}
System.out.println();
Solution solution = new Solution();
ListNode res = solution.addTwoNumbers2(l1, l4);
ListNode ans2 = solution.addTwoNumbersReview(l1, l4);
ListNode ans3 = solution.addTwoNumbersReview2(l1, l4);
while (res != null) {
System.out.print(res.val +" ");
res = res.next;
}
System.out.println();
while (ans2 != null) {
System.out.print(ans2.val +" ");
ans2 = ans2.next;
}
System.out.println();
while (ans3 != null) {
System.out.print(ans3.val +" ");
ans3 = ans3.next;
}
}
public static void main(String[] args) {
test();
}
问题不大：
9 9 9
9 9 9 9 9 9 9
8 9 9 0 0 0 0 1
8 9 9 0 0 0 0 1
8 9 9 0 0 0 0 1
总结
提示：重要经验：
1）链表的操作就是代码细节要coding清楚，其他都还好，而且链表的题目，往往就是优化空间复杂度，没啥别的骚操作
3）笔试求AC，可以不考虑空间复杂度，但是面试既要考虑时间复杂度最优，也要考虑空间复杂度最优。