LeetCode 2. 两链表整数相加生成一个和的新链表（含变异改进算法）
LeetCode ： https://leetcode-cn.com/problems/add-two-numbers/
题目描述：
给你两个非空的链表，表示两个非负的整数。
它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字（0 - 9）
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807，结果为低位到高位，即 708
示例 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 （非常重要）
题目数据保证列表表示的数字不含前导零
解题思路：
链表存储整数，是以逆序存储，即整数低位在链表头，高位在链表尾。
例如：存储整数 342，链表逆序存储即 2 -> 4 -> 3
分析如此，这样求和就可以从链表头（低位）先相加了
但是需要注意：低位相加后，有可能会有进位，如例1、例3
解法1： 正常顺序逻辑，低位相加，进位加1，最后判断一次进位是否加1 （可读性好）
时间复杂度 O(n)，空间复杂度O(1) -- 结果头结点head，sum 和 highNum
/**
* Definition for singly-linked list.
* 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) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode head = new ListNode(); // 头结点
ListNode curr = head; // 指向每次新创建节点
int highNum = 0; // 进位标识
// 同时从低位右移相加, 求和sum大于10则低位取余, 高位进1（highNum=1）
while(l1 != null && l2 != null) {
int sum = l1.val + l2.val + highNum;
highNum = 0; // 特别注意: 上一次进位求和后, 重置为0参与本次进位计算
if(sum >= 10) {
sum = sum % 10;
highNum = 1;
}
// 创建求和后的新节点, curr右移指向新节点
ListNode node = new ListNode(sum);
curr.next = node;
curr = curr.next;
l1 = l1.next;
l2 = l2.next;
}
// 若链表l2较短先遍历完了, 则继续遍历链表l1
while(l1 != null) {
int sum = l1.val + highNum;
highNum = 0;
if(sum >= 10) {
sum = sum % 10;
highNum = 1;
}
ListNode node = new ListNode(sum);
curr.next = node;
curr = curr.next;
l1 = l1.next;
}
// 若链表l1较短先遍历完了, 则继续遍历链表l2
while(l2 != null) {
int sum = l2.val + highNum;
highNum = 0;
if(sum >= 10) {
sum = sum % 10;
highNum = 1;
}
ListNode node = new ListNode(sum);
curr.next = node;
curr = curr.next;
l2 = l2.next;
}
// 若两个链表l1、l2都遍历完毕后, 还有进位则再次创建新节点, 存储最高的进位1
if(highNum == 1) {
ListNode node = new ListNode(highNum);
curr.next = node;
curr = curr.next;
}
return head.next; // 头结点的下一个节点, 才是真正和链表的最低位
}
}
解法2： 核心思想是将两个链表进行补全为等长, 较短的链表补全的节点默认数值val = 0 （即不全的后续空节点null 的val = 0）
此算法的优点是两个链表等长处理，两链表对应位的两数与进位相加（sum = l1Val + l2Val + carry），得出对应的结果位值取余（sum%10），进位整除更新（carry = sum / 10），继续循环到下一个高位参入计算
此改进算法的优点是比解法1更加的简洁，顺序逻辑，也很好理解，代码量少，干净！
时间复杂度为 O(n)，空间复杂度O(n+1)，其中+1为定义了一个临时头结点 result (val = -1)
/**
* Definition for singly-linked list.
* 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 result = new ListNode(-1); // 结果头结点, -1表示不是结果value值
ListNode curr = result; // 游标当前节点
int carry = 0; // 相加后的进位标识, 1-有进位, 0-无进位
while(l1 != null || l2 != null || carry != 0) {
int l1Val = l1 == null ? 0 : l1.val; // 核心思想, l1和l2两个链表等长, 较短链表的后续节点默认val=0
int l2Val = l2 == null ? 0 : l2.val; // 核心思想, l1和l2两个链表等长, 较短链表的后续节点默认val=0
int sum = l1Val + l2Val + carry; // 从低位到高位, 相同低位与进位相加, 链表l1和l2的val值补齐, 默认val=0
ListNode node = new ListNode(sum%10); // 取余, 存为相应的结果链表位置
carry = sum / 10; // 整除, 进位标识
curr.next = node;
curr = node;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
return result.next;
}
}
小结：
解法1 的思想是 与（ l1 && l2 ），按照链表的实际长度求和，再对较长链表进位求和，正常逻辑，好理解
解法2 的思想是 或（ l1 || l2 ），先将两个链表补全等长，即将较短链表补全的null节点默认 val = 0 再求和，也很好理解
解法3： 把链表转成整数，用整数加法求和，然后再把结果和转成链表 （思路很容易想到，但肯定会失败）
1）先把两个链表l1和l2，都转成int整型 listVal1 和 listVal2
2）然后对两个int整型数求和 sum = listVal1 + listVal2;
3）最后再把int整型结果转成链表
尝试一：链表转 int整型（Integer） （失败）
/**
* Definition for singly-linked list.
* 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 {
// 链表转int整型，求和计算，再将int转成结果链表
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1);
ListNode curr = result;
int listVal1 = 0;
int listVal2 = 0;
// 1.1 链表list1转成整型数, 例如逆序 2->4->3 转成 342
int count = 0;
while(l1 != null) {
if(count == 0) {
listVal1 = l1.val;
}
else {
listVal1 += l1.val * Math.pow(10, count);
}
count++;
l1 = l1.next;
}
// 1.2 链表list1转成整型数, 例如逆序 5->6->4 转成 465
count = 0;
while(l2 != null) {
if(count == 0) {
listVal2 = l2.val;
}
else {
listVal2 += l2.val * Math.pow(10, count);
}
count++;
l2 = l2.next;
}
System.out.printf("\n listVal1: %d, listVal2: %d", listVal1, listVal2);
// 2. 两个链表转成的整型相加 342 + 465 = 807
int sum = listVal1 + listVal2;
System.out.printf("\n%d + %d = %d", listVal1, listVal2, sum);
// 3. 最后把整型结果转成链表, 例如 807 to 7->0->8
do {
int lowNum = sum % 10;
sum = sum / 10;
ListNode node = new ListNode(lowNum);
curr.next = node;
curr = node;
} while(sum > 0);
return result.next;
}
}
/*
运行结果，不出意外，报错了
测试用例: l1 = [2,4,3], l2 = [5,6,4] 成功
测试用例: l1 = [0], l2 = [0] 成功
测试用例: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 成功
测试用例: l1 = [1,1,1,1,1,1,1,1,1,1,1], l2 = [1,1,1,1,1,1,1,1,1,1,1] 失败
预期结果: [2,2,2,2,2,2,2,2,2,2,2]
实际输出: [-2] 大数溢出了, int整数部分精度最大支持10位, 即 2^32 = 4294967296
详细调试日志如下:
listVal1: 2147483647, listVal2: 2147483647
2147483647 + 2147483647 = -2
测试用例: l1 = [9], l2 = [1,9,9,9,9,9,9,9,9,9] 失败
预期结果: [0,0,0,0,0,0,0,0,0,0,1]
实际输出: [0] 大数溢出了, int整数部分精度最大支持10位, 即 2^32 = 4294967296
详细调试日志如下:
listVal1: 9, listVal2: 2147483647
9 + 2147483647 = -2147483640
*/
尝试二：链表转 BigInteger整型 （继续失败。。。）
/**
* Definition for singly-linked list.
* 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; }
* }
*/
import java.math.BigInteger;
class Solution {
// 链表转BigInteger整型，求和计算，再将BigInteger转成结果链表
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1); // 结果头结点(额外多建的一个节点)
ListNode curr = result; // 当前节点, 不断的添加节点并移动
BigInteger bigInt1 = new BigInteger("0"); // BigInteger 需引入java包 import java.math.BigInteger;
BigInteger bigInt2 = new BigInteger("0");
// 1.1 链表list1转成整型数, 例如逆序 2->4->3 转成 342
int count = 0;
while(l1 != null) {
// int num = Integer.valueOf(l1.val + "").intValue(); // str to Integer
// int num2 = Integer.parseInt(l1.val + ""); // str to Integer
BigInteger listVal1 = BigInteger.valueOf(l1.val); // int to BigInteger
if(count == 0) {
bigInt1 = listVal1;
} else {
int intPow = new Double(Math.pow(10, count)).intValue(); // double to int, 100.000000 -> 100
BigInteger bigPow = BigInteger.valueOf(intPow); // int to BigInteger
bigInt1 = bigInt1.add( listVal1.multiply(bigPow) ); // bigInt + bigInt
}
System.out.printf("\n count: %d , listVal1: %s , bigInt1: %s", count, listVal1.toString(), bigInt1.toString());
count++;
l1 = l1.next;
}
// 1.2 链表list1转成整型数, 例如逆序 5->6->4 转成 465
count = 0;
while(l2 != null) {
BigInteger listVal2 = BigInteger.valueOf(l2.val); // int to BigInteger
if(count == 0) {
bigInt2 = listVal2;
} else {
int intPow = new Double(Math.pow(10, count)).intValue();
BigInteger bigPow = BigInteger.valueOf(intPow);
bigInt2 = bigInt2.add( listVal2.multiply(bigPow) );
}
System.out.printf("\n count: %d , listVal12: %s , bigInt2: %s", count, listVal2.toString(), bigInt2.toString());
count++;
l2 = l2.next;
}
// 2. 两个链表转成的整型相加 342 + 465 = 807
BigInteger bigSum = bigInt1.add(bigInt2);
System.out.printf("\n%s + %s = %s", bigInt1.toString(), bigInt2.toString(), bigSum.toString());
// 3. 最后把整型结果转成链表, 例如 807 to 7->0->8
do {
BigInteger lowNum = bigSum.mod(BigInteger.valueOf(10));
bigSum = bigSum.divide(BigInteger.valueOf(10));
ListNode node = new ListNode(lowNum.intValue()); // bigInt to int
curr.next = node;
curr = node;
} while(bigSum.compareTo(BigInteger.valueOf(0)) > 0);
return result.next;
}
/*
运行结果，不出意外，报错了
测试用例: l1 = [2,4,3], l2 = [5,6,4] 成功
测试用例: l1 = [0], l2 = [0] 成功
测试用例: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] 成功
测试用例: l1 = [1,1,1,1,1,1,1,1,1,1,1], l2 = [1,1,1,1,1,1,1,1,1,1,1] 失败
预期结果: [2,2,2,2,2,2,2,2,2,2,2]
实际输出: [6,1,5,9,8,1,7,1,5,6] 大数溢出了, BigInteger整数部分精度最大支持10位, 即 2^32 = 4294967296
详细调试日志如下:
count: 0 , listVal1: 1 , bigInt1: 1
count: 1 , listVal1: 1 , bigInt1: 11
count: 2 , listVal1: 1 , bigInt1: 111
count: 3 , listVal1: 1 , bigInt1: 1111
count: 4 , listVal1: 1 , bigInt1: 11111
count: 5 , listVal1: 1 , bigInt1: 111111
count: 6 , listVal1: 1 , bigInt1: 1111111
count: 7 , listVal1: 1 , bigInt1: 11111111
count: 8 , listVal1: 1 , bigInt1: 111111111
count: 9 , listVal1: 1 , bigInt1: 1111111111
count: 10 , listVal1: 1 , bigInt1: 3258594758
count: 0 , listVal12: 1 , bigInt2: 1
count: 1 , listVal12: 1 , bigInt2: 11
count: 2 , listVal12: 1 , bigInt2: 111
count: 3 , listVal12: 1 , bigInt2: 1111
count: 4 , listVal12: 1 , bigInt2: 11111
count: 5 , listVal12: 1 , bigInt2: 111111
count: 6 , listVal12: 1 , bigInt2: 1111111
count: 7 , listVal12: 1 , bigInt2: 11111111
count: 8 , listVal12: 1 , bigInt2: 111111111
count: 9 , listVal12: 1 , bigInt2: 1111111111
count: 10 , listVal12: 1 , bigInt2: 3258594758
3258594758 + 3258594758 = 6517189516
*/
说明：运行结果，不出意外，报错了
不管是把链表转成 Integer 或 BigInteger 整型数，最终都会失败，意料之中的结果。
因为整型（Integer 或 int）都会有精度的问题，一般为4个字节，2^(8*4) = 2^32 = 4294967296，即int整型最大只可表示10位数（MySQL设计int型也类似，最多10位数），若含正负符号则整数范围减半 -2147483648 ~ 2147483647，这在大一计算机基础课里都有介绍。
本算法题，用链表来做加法，本身就是为了解决大数计算问题（大数为10位数、100位数、100万位数等），我们却幼稚的又把链表转成整型数来计算，肯定会导致结果溢出！
嗯嗯，这次可以深刻的理解整型数范围（精度最大10位数）、大数加减乘除计算的原理了，也是好事儿，对吧。
实际上，我们用的Windows 计算器、MacOS 计算器、手机计算器等，本身都是支持超过10位数的大数计算的，它们进行大数计算的原理就是把大数转成长数组或链表进行计算的，感兴趣的同学可以深入去研究下计算器、圆周率、常数、天文距离的计算过程，远没有我们想得那么简单（甚至很多高级程序员，也不一定能够全部实现大数的加减整除、指数、cos、sin等科学计算功能，即做一个Windows版的计算器）
微软计算器已经开源了，详见：https://github.com/microsoft/calculator （C++写的）
为了直观解释，言之有物，我在MacOS电脑上，做了如下测试：
1）打开MacOS电脑，默认的计算器
2）计算器设置成科学计算器的界面（View - Scientific）
3）输入大整数测试，例如输入了20位大整数 乘以 2
12345678901234567890 x 2 = 24691357802469135780 = 2.469135780246913e19
20位大整数 乘以 2 = 20位大整数 = 16位精度的科学计数法 = 2.469135780246913e19 * 10^19
尝试三：链表转 BigInteger整型，全部数值计算全部用BigInteger，防止大数溢出 （成功！）
经历了上面的对 int、Integer、BigInteger的分析，我们发现超过10位数就导致溢出了
于是，深入分析【尝试二】中的代码，看是否用到了 int（Integer）类型，导致溢出
果不其然，发现在计算 pow() 时，我们用到了 int 类型，这是导致溢出的原因吗？
不要去猜，用代码去验证，用事实说话：删除int类型，全部改写成BigInteger类型，即：
// TODO intPow是整型int类型, 最大只能表示 2^32 = 4294967296 (10位数) 计算大数会溢出，舍弃 int intPow = new Double(Math.pow(10, count)).intValue(); // double to int, 100.000000 -> 100 BigInteger bigPow = BigInteger.valueOf(intPow); // int to BigInteger 改成 // TODO 全部改用BigInteger来计算大数，包含pow()，防止溢出，下同 BigInteger bigPow = BigInteger.valueOf(10).pow(count);
再次运行，发现成功通过啦！
完整代码如下：
/**
* Definition for singly-linked list.
* 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; }
* }
*/
import java.math.BigInteger;
class Solution {
// 链表转BigInteger整型，求和计算，再将BigInteger转成结果链表
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1); // 结果头结点(额外多建的一个节点)
ListNode curr = result; // 当前节点, 不断的添加节点并移动
BigInteger bigInt1 = new BigInteger("0"); // BigInteger 需引入java包 import java.math.BigInteger;
BigInteger bigInt2 = new BigInteger("0");
// 1.1 链表list1转成整型数, 例如逆序 2->4->3 转成 342
int count = 0;
while(l1 != null) {
// int num = Integer.valueOf(l1.val + "").intValue(); // str to Integer
// int num2 = Integer.parseInt(l1.val + ""); // str to Integer
BigInteger listVal1 = BigInteger.valueOf(l1.val); // int to BigInteger
if(count == 0) {
bigInt1 = listVal1;
} else {
// TODO intPow是整型int类型, 最大只能表示 2^32 = 4294967296 (10位数) 计算大数会溢出，舍弃
// int intPow = new Double(Math.pow(10, count)).intValue(); // double to int, 100.000000 -> 100
// BigInteger bigPow = BigInteger.valueOf(intPow); // int to BigInteger
// TODO 全部改用BigInteger来计算大数，包含pow()，防止溢出，下同
BigInteger bigPow = BigInteger.valueOf(10).pow(count);
bigInt1 = bigInt1.add( listVal1.multiply(bigPow) ); // bigInt + bigInt
}
System.out.printf("\n count: %d , listVal1: %s , bigInt1: %s", count, listVal1.toString(), bigInt1.toString());
count++;
l1 = l1.next;
}
// 1.2 链表list1转成整型数, 例如逆序 5->6->4 转成 465
count = 0;
while(l2 != null) {
BigInteger listVal2 = BigInteger.valueOf(l2.val); // int to BigInteger
if(count == 0) {
bigInt2 = listVal2;
} else {
// int intPow = new Double(Math.pow(10, count)).intValue();
// BigInteger bigPow = BigInteger.valueOf(intPow);
BigInteger bigPow = BigInteger.valueOf(10).pow(count);
bigInt2 = bigInt2.add( listVal2.multiply(bigPow) );
}
System.out.printf("\n count: %d , listVal12: %s , bigInt2: %s", count, listVal2.toString(), bigInt2.toString());
count++;
l2 = l2.next;
}
// 2. 两个链表转成的整型相加 342 + 465 = 807
BigInteger bigSum = bigInt1.add(bigInt2);
System.out.printf("\n%s + %s = %s", bigInt1.toString(), bigInt2.toString(), bigSum.toString());
// 3. 最后把整型结果转成链表, 例如 807 to 7->0->8
do {
BigInteger lowNum = bigSum.mod(BigInteger.valueOf(10));
bigSum = bigSum.divide(BigInteger.valueOf(10));
ListNode node = new ListNode(lowNum.intValue()); // bigInt to int
curr.next = node;
curr = node;
} while(bigSum.compareTo(BigInteger.valueOf(0)) > 0);
return result.next;
}
}
尝试四：链表转 BigDecimal整型，全部数值计算全部用BigDecimal，防止大数溢出 （继续成功！！！）
经历了上面的【尝试三】的成功，我们进一步优化代码，简化思路，步骤如下：
1）Java 中的 BigDecimal 长浮点型，是建立在 BigInteger 基础上的，改用 BigDecimal 来写试试
2）【尝试三】中把链表转成了长整型 BigInteger ，是通过 pow() 来实现的，还出错了（用了int类型导致溢出），那么我们就不用pow()，直接拼接成字符串（StringBuilder 和 StringBuffer 均可），然后反转字符串（listSB1.reverse()），再然后转成长浮点型 new BigDecimal() 来求和呢
3）对转成的两个长浮点型数 BigDecimal 进行相加，然后再把长浮点型 BigDecimal 求和后的结果转成结果字符串
4）对最后的结果字符串，也有两种处理方式
a）结果字符串反转，（字符串）从低位到高位，（结果链表）从左到右，依次链接成链表 （直观，正向思维，易理解）
b）结果字符串不反转，（字符串）从高位到低位，（结果链表）从右到左，依次链接成链表 （简洁，逆向思维，推荐）
5）对步骤4）的两种链接成链表，都实现了，且用了 if(false){……} 来进行大段代码注释，是调试中的一个小技巧
小结
此解法梳理步骤：
1）链表l1和l2 -> 拼接成字符串(从低位到高位) -> 反转字符串(从高位到低位)
2）-> 字符串转成 BigDecimal 求和
3）-> 求和结果再转回到字符串 -> 对字符串逐个字符进行拼接 -> 链接成最终的链表
完整代码如下，已通过运行
/**
* Definition for singly-linked list.
* 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; }
* }
*/
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.*;
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(-1);
ListNode curr = result;
StringBuilder listSB1 = new StringBuilder();
StringBuilder listSB2 = new StringBuilder();
// 1.1 链表l1转成字符串 2->4->3 to 243
while(l1 != null) {
listSB1.append(l1.val);
l1 = l1.next;
}
// 1.2 链表l1转成字符串 5->6->4 to 564
while(l2 != null) {
listSB2.append(l2.val);
l2 = l2.next;
}
// 2. 反转字符串后，转成BigDecimal，再相加求和
BigDecimal bigVal1 = new BigDecimal(listSB1.reverse().toString()); // 243 to 342
BigDecimal bigVal2 = new BigDecimal(listSB2.reverse().toString()); // 243 to 342
BigDecimal bigSum = bigVal1.add(bigVal2); // 342 + 465 = 807
System.out.printf("\n %s + %s = %s", bigVal1.toString(), bigVal2.toString(), bigSum.toString());
if(false) {
// 3. 将结果和，再反转成从低位到高位
String strResult = new StringBuffer(bigSum.toString()).reverse().toString(); // 807 to 708
System.out.printf("\nstrResult : %s", strResult);
// 4. 最后将和结果，从低位到高位，链接成链表
for(int i=0; i<strResult.length(); i++) {
ListNode node = new ListNode(strResult.charAt(i) - '0'); // 字符串相减得整数值, 例如 '0' - '0' = 0
curr.next = node;
curr = node;
}
return result.next;
}
// 以上的步骤3与4，也可以合成在一起，从高位到低位逆向链接成链表 807 to 7->0->8
String strResult2 = bigSum.toString(); // 807
ListNode result2 = null;
for(int i=0; i<strResult2.length(); i++) {
ListNode node = new ListNode(strResult2.charAt(i) - '0');
node.next = result2;
result2 = node;
}
return result2;
}
}
点评：
解法3的【尝试一、二】，用到了 int（Integer），当链表超过10个节点(超出10位数)，会溢出报错，失败！
解法3的【尝试三、四】，用到了Java特有的 BigInteger、BigDecimal 等大数类型，在其它编程语言中并不通用，例如 C/C++、Python、PHP、Golang等编程语言并不支持大数类型，且更重要的是大数计算并不会转成整型（或浮点型）来求解，本末倒置了，因此解法3并不推荐。
解法4： 递归算法，并且递归遍历了两次：
第一次遍历：创建求和的链表（结果链表）
第二次遍历：在第一次遍历的基础上，从最左侧(最低位)判断是否有进位, 若有进位则再次递归一次两个链表的求和过程（跟第一次遍历求和两个链表一样），不同的是：这次求和遍历的链表之一是进位链表（new ListNode(sum/10) ），有且仅有一个元素, 即进位元素（new ListNode(sum/10)）
递归算法的核心难点和精妙处：
1）第二次遍历时, sum此处的值, 有且仅有在上面第一次递归出栈后，存储的链表l1和l2最左侧头结点(即最低位)求和后的进位（多读几遍，在纸上和脑海里多递归几遍，step by step，您就懂了，哈哈哈 ）
2）进位只有可能从最低位依次累加到最高位，即从左到右逐次累加进位，可参考 输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
/**
* Definition for singly-linked list.
* 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) {
if(l1 == null) return l2;
if(l2 == null) return l1;
// 第一次从左递归遍历链表, 创建结果和的链表
int sum = l1.val + l2.val;
ListNode head = new ListNode(sum % 10); // 存储相加结果和的链表, 从左到右
head.next = addTwoNumbers(l1.next, l2.next);
// 第二次从左递归遍历链表
// 若节点相加的结果和有进位(大于等于10), 则创建一个只有一个节点的链表与和链接一起递归, 从左到右
// 特别注意: sum此处的值, 有且仅有在上面第一次递归出栈后, 存储的链表l1和l2最左侧头结点(即最低位)求和后的进位, 这是此道题用递归算法最精妙也是最难理解的地方, 哈哈哈
if(sum >= 10) {
head.next = addTwoNumbers(new ListNode(sum/10), head.next);
}
return head;
}
}
上面的两次递归遍历，估计还是有很多同学没搞明白具体的递归流程细节
这里，我稍作了测试用例的巧妙设计，通过打印详细的递归日志一窥奥秘：
日志调试用例： 输入 l1 = [7,4,3], l2 = [5,6,4], 预期结果 = [2,1,8]
/**
* Definition for singly-linked list.
* 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 void printList(String tag, int sum, ListNode list) {
System.out.printf("\n%s +++ sum=%d , head list: ", tag, sum);
while(list != null) {
if(list.next != null) {
System.out.print(list.val + " -> ");
}
else {
System.out.print(list.val);
}
list = list.next;
}
}
// 测试用例
// 输入 l1 = [7,4,3], l2 = [5,6,4], 预期结果 = [2,1,8] ++++ 日志调试用例
// 输入 l1 = [9,9,9], l2 = [9,9]
// 输入 l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
// 输入 l1 = [0], l2 = [0]
int count = 0; // 递归循环执行次数, 仅做调试日志使用
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
// 第一次从左递归遍历链表, 创建结果和的链表
int sum = l1.val + l2.val;
ListNode head = new ListNode(sum % 10); // 存储相加结果和的链表, 从左到右
count++;
System.out.printf("\n\ncount = " + count + " , sum = " + sum + " , head.val = " + head.val + " , head.hash = " + head.hashCode());
printList("1 - before", sum, head);
head.next = addTwoNumbers(l1.next, l2.next);
printList("1 - after", sum, head);
// 第二次从左递归遍历链表
// 若节点相加的结果和有进位(大于等于10), 则创建一个只有一个节点的链表与和链接一起递归, 从左到右
// 特别注意: sum此处的值, 有且仅有在上面第一次递归出栈后, 存储的l1和l2最左侧头结点(即最低位)求和后的进位, 这是此道题用递归算法最精妙也是最难理解的地方, 哈哈哈
if(sum >= 10) {
printList("2 - before", sum, head);
head.next = addTwoNumbers(new ListNode(sum/10), head.next);
printList("2 - after", sum, head);
}
printList("result", sum, head);
return head;
}
}
/*
输入 [7,4,3] [5,6,4]
输出 [2,1,8]
预期结果 [2,1,8]
打印日志，调试的输出结果：
count = 1 , sum = 12 , head.val = 2 , head.hash = 112061925
1 - before +++ sum=12 , head list: 2
count = 2 , sum = 10 , head.val = 0 , head.hash = 724125922
1 - before +++ sum=10 , head list: 0
count = 3 , sum = 7 , head.val = 7 , head.hash = 1843368112
1 - before +++ sum=7 , head list: 7
1 - after +++ sum=7 , head list: 7
result +++ sum=7 , head list: 7
1 - after +++ sum=10 , head list: 0 -> 7
2 - before +++ sum=10 , head list: 0 -> 7
count = 4 , sum = 8 , head.val = 8 , head.hash = 120694604
1 - before +++ sum=8 , head list: 8
1 - after +++ sum=8 , head list: 8
result +++ sum=8 , head list: 8
2 - after +++ sum=10 , head list: 0 -> 8
result +++ sum=10 , head list: 0 -> 8
1 - after +++ sum=12 , head list: 2 -> 0 -> 8
2 - before +++ sum=12 , head list: 2 -> 0 -> 8
count = 5 , sum = 1 , head.val = 1 , head.hash = 916419490
1 - before +++ sum=1 , head list: 1
1 - after +++ sum=1 , head list: 1 -> 8
result +++ sum=1 , head list: 1 -> 8
2 - after +++ sum=12 , head list: 2 -> 1 -> 8
result +++ sum=12 , head list: 2 -> 1 -> 8
*/
小结
递归算法，需要考虑的细节太多，特别是逻辑和边界，要非常清晰，才可能写出来
在面试环节的短短一二十分钟内，若没有提前递归训练和深入思考，是很难写出来的
毕业工作了好多年，虽然项目中也会写一些数据结构和队列算法，但好些年没面试，没写算法了，这道题我是第一次遇到，心里知道能用递归求解，但在面试算法环节里，要深入逻辑分析和边界考虑，面试时间太短，一时半会儿没写出来，果断改用写的是Stack栈结构来求解的（先解决问题，再考虑优化），算法直观，通俗易懂，但代码不够简洁（见上面的解法1），用了已有的Stack栈结构和大量的额外存储空间，来替代了递归算法。
在实际项目中，尽量少用栈递归算法，为什么呢？
因为在我的工作项目中（最典型的案例是扫雷游戏，很多年前在创新工场写过Android游戏，扫雷游戏就是我做的，花了一周时间支持30x30, 50x50, 100x100, 500x500, 可自定义 x*y 的扫雷地图，搜索当前地雷点周围的8个方格的地雷个数，及其这8个方格里有地雷的下一个8个方格的地雷数，并依次递归完全部扫雷地图，很适合用递归算法的场景），曾经因为代码里用了递归算法，递归压栈层次太深，导致了栈内存溢出（Stack OverFlow），这是因为JVM虚拟机或操作系统，在分配内存资源（CPU寄存器、CPU高速缓存第一级L1、内存管理器申请内存大小）时，分配到栈帧的大小是有限的，例如 32KB、64KB、256KB、1MB等，压栈层级太深太多了，容易导致栈内存大小耗尽，不够了导致栈溢出报错。
我们简单计算下栈大小与链表长度的关系：
64位操作系统，每个int整型4个字节，指针长度8个字节(64bit)
链表长度100个节点(ListNode)，每个节点包含一个int整型4个字节，一个节点(ListNode)8个字节
考虑到64位操作系统需要填充对齐，因此一个递归节点的长度 4 + 8 + 4(填充对齐) = 16个字节
一个链表长度为100个节点，即 100节点 * 16字节 = 1600字节，远小于32KB最小的栈帧大小
因此，此题木可以放心的使用递归来求解（这也是题目设定链表长度为100，不能太长的原因）
思考：32KB / 16字节 = 2K = 2000个节点(ListNode)，即递归最长链表长度为2000个节点
更多堆栈的内存大小分配，请见米扑博客：
栈大小计算初探
操作系统分配给每个进程的内存是有限制的。
可用的栈内存 = 进程最大内存 - 堆内存 - 方法区内存 - 程序计数器内存 - 虚拟机本身耗费内存
栈是线程私有的，可以认为：
程序可建立的线程数量 = 可用栈内存 / 栈大小
当栈大小设置太大时，就会导致创建的线程数量太少。
这样在多线程的情况下，便可能发生“内存溢出”情况。
-Xss 为JVM启动的每个线程分配的内存大小，
默认JDK1.4中是256K，JDK1.5+中是1M，这在JVM虚拟机设置
也有文档为操作系统默认栈大小为8MB，跟JVM虚拟机还不一样
在X64位Linux操作系统上，JVM默认的栈大小为1MB = 1024KB
由于程序要支持高并发场景，所以4个线程每个线程栈的大小为256KB，以上仅供参考。
不用栈递归算法，用什么替代呢？
答案：
1）使用循环解决，例如解法1，多次 while 循环，压栈可以改用队列（数组和链表），彻底解决栈溢出
2）使用队列（数组和链表） + 层次优先遍历，队列存储当前的栈顶状态，层次遍历解决栈的深度问题（扫雷游戏的最终解决方案）
3）若一定要使用递归，请预先判定限制递归的深度数，层次不要太深；使用尾递归，尾递归是指在方法返回时只调用自己本身，且不能包含表达式。编译器或解释器会把尾递归做优化，使递归方法不论调用多少次，都只占用一个栈帧，所以不会出现栈溢出。注意：Java没有尾递归优化。
知识点拓展
尾递归：如果一个函数中所有递归形式的调用都出现在函数的末尾，我们称这个递归函数是尾递归的。当递归调用是整个函数体中最后执行的语句且它的返回值不属于表达式的一部分时，这个递归调用就是尾递归。尾递归函数的特点是在回归过程中不用做任何操作，这个特性很重要，因为大多数现代的编译器会利用这种特点自动生成优化的代码。
int facttail(int n, int a)
{
if (n < 0)
return 0;
else if (n == 0)
return 1;
else if (n == 1)
return a;
else
return facttail(n - 1, n * a);
}
当编译器检测到一个函数调用是尾递归的时候，它就覆盖当前的活动记录而不是在栈中去创建一个新的。编译器可以做到这点，因为递归调用是当前活跃期内最后一条待执行的语句，于是当这个调用返回时栈帧中并没有其他事情可做，因此也就没有保存栈帧的必要了。通过覆盖当前的栈帧而不是在其之上重新添加一个，这样所使用的栈空间就大大缩减了，这使得实际的运行效率会变得更高。
在函数式语言Erlang中（亦是栈语言），如果想要保持语言的高并发特性，就必须用尾递归来替代传统的递归。
尾递归的示例
// 线性递归:
long Rescuvie(long n) {
return (n == 1) ? 1 : n * Rescuvie(n - 1);
}
// 尾递归:
long TailRescuvie(long n, long a) {
return (n == 1) ? a : TailRescuvie(n - 1, a * n);
}
// 对比分析
当n = 5时
对于线性递归, 他的递归过程如下:
Rescuvie(5)
{5 * Rescuvie(4)}
{5 * {4 * Rescuvie(3)}}
{5 * {4 * {3 * Rescuvie(2)}}}
{5 * {4 * {3 * {2 * Rescuvie(1)}}}}
{5 * {4 * {3 * {2 * 1}}}}
{5 * {4 * {3 * 2}}}
{5 * {4 * 6}}
{5 * 24}
120
对于尾递归, 他的递归过程如下:
TailRescuvie(5)
TailRescuvie(5, 1)
TailRescuvie(4, 5)
TailRescuvie(3, 20)
TailRescuvie(2, 60)
TailRescuvie(1, 120)
120
小结
很容易看出, 普通的线性递归比尾递归更加消耗资源
在实现上说, 每次重复的过程调用都使得调用链条不断加长
系统不得不使用栈进行数据保存和恢复
而尾递归就不存在这样的问题, 因为他的状态完全由n和a保存
变异改进算法 （上面的LeetCode题目描述，改动一个字 "逆序" 改为了 "正序"）
题目描述：
给你两个非空的链表，表示两个非负的整数。
它们每位数字都是按照正序（变异改进点）的方式存储的，并且每个节点只能存储一位数字（0 - 9）
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
解释：243 + 564 = 807 （变异改进点：正序，从高位到低位）
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[1,9,9,9,0,0,0,8] （变异改进点：正序，从高位到低位）
示例 4：
输入：l1 = [1,2,3,6], l2 = [3,5] 即 1->2->3->6 和 3->5
输出：[1,2,7,1] ，即 1->2->7->1（变异改进点：正序，从高位到低位）
提示：
每个链表中的节点数在范围 [1, 100] 内
0 <= Node.val <= 9 （非常重要）
题目数据保证列表表示的数字不含前导零
解题思路：
有了本文上面的LeetCode算法题"逆序"的四种解法，我们很容易想到本题"正序"的四种解法：
1）先把本题"正序" 输入的两个正序链表l1和l2，分别做一次链表反转，转成两个"逆序"的链表
2）把反转的两个"逆序"的链表，套用上面LeetCode的四种解法，求出"逆序"的结果链表
3）最后把"逆序"的结果链表，再做一次链表反转，即得到了"正序"的结果链表
简言之，"正序" -> 反转成"逆序" -> "逆序"计算 -> "逆序"结果 -> 反转成"正序"结果
站在前人的肩膀上来求解，很容易想到，但也像画蛇添足，放屁脱裤子——多此一举
解法1：把"正序"链表反转为"逆序"链表，然后用上面的解法1-4解答
这里，仅给出链表反转的算法，如下：
public ListNode reverseList(ListNode head) {
ListNode result = null;
ListNode curr = head;
// 1->2->3->4->5->NULL
// 1->NULL 2->3->4->5->NULL
// 2->1->NULL 3->4->5->NULL
// 3->2->1->NULL 4->5->NULL
// 4->3->2->1->NULL 5->NULL
// 5->4->3->2->1->NULL NULL
int count = 0;
while(curr != null) {
ListNode next = curr.next; // 2
curr.next = result; // null
result = curr; // 1
curr = next; // 2
// printList(count, result, curr);
count++;
}
return result;
}
链表反转的更多算法，请见米扑博客：
LeetCode 206 反转链表 （while迭代，stack()栈实现，递归、尾递归等共四种算法）
上面的解题思路，显然不是面试官对面试者考察的真实意图，转来转去把面试官都给转晕了。。。
然而，很不幸，我遇到的真实面试题，就是本题输入"正序"的两个链表，输出"正序"的结果链表
然而，很庆幸，我没有练过算法，根本就不知道上面LeetCode算法题，所以我是临场发挥的，哈哈哈
花絮随风去，正题请出来，下面真实的给出我当时临场发挥的心理历程，敬请斧正、指点、交流，谢谢。
解法2： 使用Stack()栈来辅助求解，直观、简单、易懂 （可读性好）
先看给出的两个示例：
1）输入：l1 = [2,4,3], l2 = [5,6,4] 输出：[8,0,7] // 有进位
输入：l1 = 2->4->3 , l2 = 5->6->4 , 输出 8->0->7
2）输入：l1 = [1,2,3,6], l2 = [3,5] 输出：[1,2,7,1] // 有进位
输入：l1 = 1->2->3->6 , l2 = 3->5 , 输出 1->2->7->1
解题思路：
1）先把"正序"的两个链表压入栈 Stack()
2）然后两个栈顶（低位）弹出相加，和结果取余存到另一个结果栈里Stack()
3）最后把结果栈弹出，依次拼接成结果链表
解法3：
总结
面试的题目千变万化，算法的灵魂始终如一
好看的皮囊千篇一律，有趣的灵魂万里挑一
算法的更高境界，是一种智慧、思想与哲学
参考推荐：
LeetCode 543. 二叉树的直径 (任意两结点最长距离)
LeetCode 206 反转链表 （推荐先看）
LeetCode 2. 两链表整数相加生成一个和的新链表（含变异改进算法）
Python 常用加密算法 base64, md5, sha1
版权所有: 本文系米扑博客原创、转载、摘录，或修订后发表，最后更新于 2021-02-19 12:23:18
侵权处理: 本个人博客，不盈利，若侵犯了您的作品权，请联系博主删除，莫恶意，索钱财，感谢！