01.俩数相加

Code

题目

给你两个   非空 的链表，表示两个非负的整数。它们每位数字都是按照   逆序   的方式存储的，并且每个节点只能存储   一位   数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

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

• 输入：l1 = [2,4,3], l2 = [5,6,4]
• 输出：[7,0,8]
• 解释：342 + 465 = 807.

base

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = (l1, l2) => {
	let num1 = +l1.reverse().join("");
	let num2 = +l2.reverse().join("");
	return num1 + num2;
};

Optimization

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function (l1, l2) {
	// 进位数
	let carry = 0;
	// 哨兵节点
	let preNode = new ListNode(-1);
	let currentNode = preNode;
	while (l1 || l2) {
		// 当前位的数值和
		let sum = ((l1 && l1.val) || 0) + ((l2 && l2.val) || 0) + carry;
		carry = Math.floor(sum / 10);
		let value = sum % 10;
		currentNode.next = new ListNode(value);
		currentNode = currentNode.next;
		l1 = l1 && l1.next;
		l2 = l2 && l2.next;
	}

	if (carry) {
		currentNode.next = new ListNode(carry);
	}

	return preNode.next;
};

Advanced

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
const addTwoNumbers = (l1, l2) => {
	let head = null;
	let tail = null;
	let carry = 0;

	while (l1 || l2) {
		const n1 = l1 ? l1.val : 0;
		const n2 = l2 ? l2.val : 0;
		const sum = n1 + n2 + carry;
		if (!head) {
			head = tail = new ListNode(sum % 10);
		} else {
			tail.next = new ListNode(sum % 10);
			tail = tail.next;
		}
		carry = Math.floor(sum / 10);
		if (l1) {
			l1 = l1.next;
		}
		if (l2) {
			l2 = l2.next;
		}
	}
	if (l1) {
		l1 = l1.next;
	}
	if (l2) {
		l2 = l2.next;
	}
	if (carry > 0) {
		tail.next = new ListNode(carry);
	}
	return head;
};

思想

top1

利用 js 中的 reverse() 将数组进行翻转，然后利用 join('') 把数组拼接成字符串，然后通过 + 进行隐式转换

top2

利用链表中哨兵思想

top3

• 由于输入的俩个链表都是逆序存储数字的位数的，因此两个链表中同一位置的数字可以直接相加。
• 我们同时遍历两个链表，逐位计算它们的和，并与当前位置的进位值相加。具体而言，如果当前两个链表处相应位置的数字为 n1,n2，进位值为 carry ，则它们的和为 n1+n2+carry。
• 其中，答案链表处相应位置的数字为 （n1+n2+carry）%10 ，而新的进位值为 Math.floor(（n1+n2+carry）/10)。
• 如果两个链表的长度不同，则可以认为长度短的链表的后面有若干个 0 。
• 此外，如果链表遍历结束后，有 carry>0，还需要在答案链表的后面附加一个节点，节点的值为 carry。

top4

因为链表是逆序存储的，我们直接模拟加法，处理好进位就可以了。

• 使用哑结点（dummy），不用对头结点是否存在单独判断; 声明一个 carry 变量用于存储进位。
• x 的值为 l1 的 val，如果走到 l1 的尾部，设置为 0
• y 的值为 l2 的 val, 如果走到 l2 的尾部， 设置为 0
• 求和： sum = val1 + val2 + carry
• 求进位：Math.floor(sum / 10)
• 求链表对应的新值：sum % 10
• 创建新的结点，将新结点添加到链表中，并更新当前链表： cur = cur.next
• 更新 l1 和 l2

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */

var addTwoNumbers = function (l1, l2) {
	const dummy = new ListNode(0);
	let curr = dummy;
	let carry = 0;
	while (l1 !== null || l2 !== null || carry !== 0) {
		let x = l1 ? l1.val : 0;
		let y = l2 ? l2.val : 0;
		let sum = x + y + carry;
		carry = Math.floor(sum / 10);
		curr.next = new ListNode(sum % 10);
		curr = curr.next;
		l1 = l1 ? l1.next : null;
		l2 = l2 ? l2.next : null;
	}

	return dummy.next;
};