两数相加（2）

题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例

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

原因：342 + 465 = 807

算法

迭代

新建一个链表sumList和用来存储进位的变量decimal，迭代两个链表，每次相加对应的节点（如果节点不存在则填充0）和进位作为新节点的val，然后将sunList.next指向这个新的节点，如果l1或l2没有指向链表尾部则向后移动一个节点，然后继续迭代

直到两个节点指针都移动到各自的链表尾部，跳出循环，然后判断变量decimal是否有进位的1，如果有则将尾部节点指向new ListNode(1)，否则指向null

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const addTwoNumbers = (l1, l2) => {
	let sumList = new ListNode();
	let listHead = sumList;
	let decimal = 0;
	while (l1 || l2) {
		let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + decimal;
		decimal = ~~(sum / 10);
		sumList.next = new ListNode(sum % 10);
		sumList = sumList.next;
		l1 ? (l1 = l1.next) : null;
		l2 ? (l2 = l2.next) : null;
	}
	sumList.next = decimal ? new ListNode(decimal) : null;
	return listHead.next;
};

递归

递归的参数：链表l1和l2，进位的变量carry 递归的返回：本地递归操作后（保存了对应位的值的和）的节点 递归的结束：链表l1、l2指向结尾且进位carry为0时，返回null 递归的过程：新建节点node，求出对应位置的和（如果该节点不存在填充0），取出末位赋值给node.val，取出十位赋值给carry，将该节点node.next指向内层递归返回的节点

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
export const addTwoNumbers = (l1, l2) => {
	let carry = 0;
	function recursion(l1, l2, carry) {
		if (!l1 && !l2 && !carry) return null;
		let sum = (l1 ? l1.val : 0) + (l2 ? l2.val : 0) + carry;
		let node = new ListNode(sum % 10);
		node.next = recursion(l1 ? l1.next : null, l2 ? l2.next : null, ~~(sum / 10));
		return node;
	}
	return recursion(l1, l2, carry);
};