切换主题
求和链表篇
逆序储存
解题思路
因为链表是逆序存储的，我们直接模拟加法，处理好进位就可以了：
- 使用哑节点
dummy，不用对头节点是否存在单独判断; 声明一个carry变量用于存储进位； v1的值为l1的val，如果走到l1的尾部，设置为0；v2的值为l2的val, 如果走到l2的尾部，设置为0；- 求和：
sum = val1 + val2 + carry； - 求进位：
Math.floor(sum / 10)； - 求链表对应的新值：
sum % 10； - 创建新的节点，将新节点添加到链表中，并更新当前链表：
cur = cur.next； - 更新
l1和l2。
JavaScript
const addTwoNumbers = (l1, l2) => {
const dummy = new ListNode(-1)
let [curr, carry] = [dummy, 0]
while (carry || l1 || l2) {
let v1 = l1 ? l1.val : 0
let v2 = l2 ? l2.val : 0
const sum = v1 + v2 + carry
carry = ~~(sum / 10)
curr.next = new ListNode(sum % 10)
curr = curr.next
l1 = l1 ? l1.next : null
l2 = l2 ? l2.next : null
}
return dummy.next
}时间复杂度：O(max(m,n))；空间复杂度：O(1)。
正序储存
反转链表再求和
解题思路
因为链表是正序存储的，我们需要先反转链表，再模拟加法。
这个就不贴代码了！！！
时间复杂度：O(max(m,n))；空间复杂度：O(1)。
栈方法
JavaScript
const addTwoNumbers = (l1, l2) => {
const [s1, s2] = [[], []]
while (l1 || l2) {
if (l1) {
s1.push(l1.val) // 入栈
l1 = l1.next
}
if (l2) {
s2.push(l2.val) // 出栈
l2 = l2.next
}
}
let [head, carry] = [null, 0]
while (carry || s1.length || s2.length) {
const v1 = s1.length ? s1.pop() : 0
const v2 = s2.length ? s2.pop() : 0
const sum = v1 + v2 + carry
carry = ~~(sum / 10)
// 此时为正序
const curr = new ListNode(sum % 10)
curr.next = head
head = curr
}
return head
}时间复杂度：O(max(m,n))；空间复杂度：O(m+n)。