两数相加II（445）

题目

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例

输入：(7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4) 输出：7 -> 8 -> 0 -> 7

算法

栈 + 翻转

先将两个链表中数字依次放入栈，然后依次弹出栈顶元素（低位），然后相加，使用变量carry来保存进位，只要stack1不为空或者stack2不为空或者进位carry不为0，我们就仍需要生成较高位节点，最后生成一个低位到高位的链表，然后翻转这个链表并返回

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
const addTwonumbers = (l1, l2) => {
	const stack1 = [],
		stack2 = [];
	while (l1) {
		stack1.push(l1.val);
		l1 = l1.next;
	}
	while (l2) {
		stack2.push(l2.val);
		l2 = l2.next;
	}
	const sentinel = new ListNode();
	let node = sentinel;
	let carry = 0;
	while (stack1.length && stack2.length) {
		const index = stack1.pop() + stack2.pop() + carry;
		node.next = new ListNode(index % 10);
		carry = ~~(index / 10);
		node = node.next;
	}
	while (stack1.length) {
		const index = stack1.pop() + carry;
		node.next = new ListNode(index % 10);
		carry = ~~(index / 10);
		node = node.next;
	}
	while (stack2.length) {
		const index = stack2.pop() + carry;
		node.next = new ListNode(index % 10);
		carry = ~~(index / 10);
		node = node.next;
	}
	if (carry !== 0) {
		node.next = new ListNode(carry);
	}
	const reverse = (node) => {
		if (!node.next) return node;
		let head = reverse(node.next);
		node.next.next = node;
		node.next = null;
		return head;
	};
	return reverse(sentinel.next);
};

栈

我们不必像方法一中一样，判断stack1和stack2是否位空，或者进位变量carry是否不为0，我们使用或||运算一次性判断，只要其中一个不满足则说明高位仍然有节点，此时我们将空的栈进行补0操作

我们使用变量res来保存每次生成的新节点（高位节点），然后每次生成新的高位节点后指向上一轮的res（即前一位），然后我们将变量res指向新的最高位，最后的结果返回这个变量res即可

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
const addTwonumbers = (l1, l2) => {
	const stack1 = [],
		stack2 = [];
	while (l1) {
		stack1.push(l1.val);
		l1 = l1.next;
	}
	while (l2) {
		stack2.push(l2.val);  
		l2 = l2.next;
  }
  
	let carry = 0;
	let res = null;
	while (stack1.length || stack2.length || carry !== 0) {
		const num1 = stack1.length ? stack1.pop() : 0;
		const num2 = stack2.length ? stack2.pop() : 0;
		const index = num1 + num2 + carry;
		let curNode = new ListNode(index % 10);
		carry = ~~(carry / 10);
		curNode.next = res;
		res = curNode;
	}
	return res;
};