辅助栈 + 头插法
解题思路
迭代两个链表的值放入两个栈中；
利用两个栈计算每一位的值，判断是否进位；
利用头插法构建链表；
复杂度
-
时间复杂度：
O(max(m,n))，其中 m 和 n 分别为两个链表的长度，需要遍历两个链表的全部位置，而处理每个位置只需要O(1)的时间； -
空间复杂度：
O(m + n)，其中 m 和 n 分别为两个链表的长度，空间复杂度主要取决于把链表内容放入栈中所用的空间；
代码实现
var addTwoNumbers = function (l1, l2) {
// 1. 声明两个辅助栈，将 l1、l2 放入辅助栈中
let stack1 = [];
let stack2 = [];
while (l1) {
stack1.push(l1.val);
l1 = l1.next;
}
while (l2) {
stack2.push(l2.val);
l2 = l2.next;
}
// 2. 两个辅助栈依次出栈栈顶元素进行相加
let curr = null;
let addOne = 0;
while (addOne || stack1.length || stack2.length) {
let val1 = stack1.length ? stack1.pop() : 0;
let val2 = stack2.length ? stack2.pop() : 0;
let sum = val1 + val2 + addOne;
addOne = sum >= 10 ? 1 : 0;
// 3. 利用头插法构建链表
let currNode = new ListNode(sum % 10, curr);
curr = currNode;
}
return curr;
};
反转链表
解题思路
将 l1、l2 反转 l1‘、l2’；
计算 l1‘ 和 l2’ 的链表每一位进行求和，并加上 进位 ，更新此次求和是否要 进位 ，生成 l3；
返回 l3 反转后的结果
复杂度
时间复杂度：
O(max(m,n))，其中 m 和 n 分别为两个链表的长度，需要遍历两个链表的全部位置，而处理每个位置只需要O(1)的时间；空间复杂度：
O(1)
实现代码
var addTwoNumbers = function (l1, l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
let l3 = addTwo(l1, l2);
return reverseList(l3);
}
var reverseList = function (head) {
// 记录上一个节点
let prev = null
// 记录当前节点
let cur = head
// 当 cur 是节点时，进行迭代
while (cur) {
// 先保存当前节点的下一个节点
const next = cur.next
// 反转链表
cur.next = prev
// 向下移动链表
prev = cur
// 取出存储的节点，继续循环
cur = next
}
return prev
};
var addTwo = function (l1, l2) {
let dmg = new ListNode(0, null);
let curr = dmg;
let addOne = 0;
while (l1 || l2 || addOne) {
let val1 = l1 ? l1.val : 0;
let val2 = l2 ? l2.val : 0;
let sum = val1 + val2 + addOne;
addOne = sum >= 10 ? 1 : 0;
curr.next = new ListNode(sum % 10, null);
curr = curr.next;
l1 && (l1 = l1.next);
l2 && (l2 = l2.next);
}
return dmg.next;
};
打赏作者
您的打赏是我前进的动力
微信
支付宝
leetcode🧑💻 2. 两数相加
上一篇
评论
