网络异常，图片无法展示
|
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
网络异常，图片无法展示
|
输入： l1 = [7,2,4,3], l2 = [5,6,4] 输出： [7,8,0,7] 复制代码
示例2：
输入： l1 = [2,4,3], l2 = [5,6,4] 输出： [8,0,7] 复制代码
示例3：
输入： l1 = [0], l2 = [0] 输出： [0] 复制代码
提示：
- 链表的长度范围为
[1, 100] 0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
进阶： 如果输入链表不能翻转该如何解决？
本题要我们将输入字符串代表的数字相加，依然通过链表头节点存储数字最高位的方式返回结果链表
又因为本题要求不翻转链表完成本题，所以我们可以通过栈存储输入链表每个节点的值
因为输入链表头节点存储其对应数字的最高位的值，而且栈是先进后出的数据结构，所以最后栈顶的值，对应的就是数字个位的数值
这样初始将两个栈栈顶元素取出，其对应的就是输入链表对应两个数字的个位的数值，将两个数字相加，根据和值即可确定输入链表对应数字和值的个位数字，依次类推，就可以确定两个输入数字和值的每一位的值
通过每一个位的值即可构建结果链表
解题思路如下：
- 创建两个栈，初始化为空数组，存储输入链表每一个节点的值
- 遍历输入链表，将每个节点的
val压入对应的栈 - 每次取出两个栈的栈顶元素相加，根据和值确定输入链表对应两数相加和值当前位的数字。需要注意的是相加大于等于
10的时候需要记录进位数 - 根据当前位的数字构建结果链表，这里需要注意的是因为题目要求结果链表数字最高位位于链表头节点，而我们初始求得的是个位的值，然后十位，百位...，所以构建结果链表的时候需要倒序构建
- 最后当两个栈都为空，需要判断进位值是否为
0，如果进位值不为0,则需要根据进位值创建节点，并连接在结果链表的前面
整体过程如下：
网络异常，图片无法展示
|
代码如下：
var addTwoNumbers = function(l1, l2) { // 初始化两个栈存储输入链表的数字 const stack1 = [], stack2 = []; while(l1){ stack1.push(l1.val); l1 = l1.next; } while(l2){ stack2.push(l2.val); l2 = l2.next; } // 初始化进位数为0 let carry = 0, res = null; // 每次取出栈顶值，初次栈顶值为两个链表对应数字的个位数 // 将两个数字相加，根据和值构建结果链表 // 因为结果链表要求数字最高位在链表头节点，而以下过程得到的数字结果为从低位到高位，所以构建结果链表的过程为倒序构建 while(stack1.length || stack2.length){ const sum = (stack1.pop()||0)+(stack2.pop()||0)+carry; const node = new ListNode(sum%10); carry = Math.floor(sum/10); node.next = res; res = node; } if(carry){ const node = new ListNode(carry); node.next = res; res = node; } return res; }; 复制代码
至此我们就完成了 leetcode-leetcode-445-两数相加II
如有任何问题或建议，欢迎留言讨论！
