快手算法：链表求和

[sisterAn]

给定两个用链表表示的整数，每个节点包含一个数位。

这些数位是反向存放的，也就是个位排在链表首部。

编写函数对这两个整数求和，并用链表形式返回结果。

示例：

输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912
进阶：思考一下，假设这些数位是正向存放的，又该如何解决呢?

示例：

输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

leetcode

[dinjufen]

用carry存储每次的进位

var addTwoNumbers = function(l1, l2) {
 let carry = 0;
 let root = new ListNode(0)
 let p = root;
 while (l1 || l2) {
 let sum = 0
 if (l1) {
 sum += l1.val
 l1 = l1.next
 }
 if (l2) {
 sum += l2.val
 l2 = l2.next
 }
 sum += carry
 carry = Math.floor(sum / 10)
 p.next = new ListNode(sum % 10)
 p = p.next
 }
 if (carry === 1) {
 p.next = new ListNode(carry)
 p = p.next
 }
 return root.next
};

[syc666]

进阶部分，先把两个链表倒置，再相加

function fn(l1, l2) {
 //函数导致
	const reverseFn = (l) => {
		let prev = null,
			curr = l
		while (curr) {
			const temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		}
		return prev
	}
	const reverseL1 = reverseFn(l1)
 const reverseL2 = reverseFn(l2)
 
 //单个链表计算
	const sumFn = (l) => {
		let n = 1,
			sum = 0
		while (l) {
			sum += n * l.val
			l = l.next
			n = n * 10
		}
		return sum
	}
	const res = sumFn(reverseL1) + sumFn(reverseL2)
	return res
}

[MickWang]

进阶部分，先把两个链表倒置，再相加

function fn(l1, l2) {
 //函数导致
	const reverseFn = (l) => {
		let prev = null,
			curr = l
		while (curr) {
			const temp = curr.next
			curr.next = prev
			prev = curr
			curr = temp
		}
		return prev
	}
	const reverseL1 = reverseFn(l1)
 const reverseL2 = reverseFn(l2)
 
 //单个链表计算
	const sumFn = (l) => {
		let n = 1,
			sum = 0
		while (l) {
			sum += n * l.val
			l = l.next
			n = n * 10
		}
		return sum
	}
	const res = sumFn(reverseL1) + sumFn(reverseL2)
	return res
}
``

直接转化为数字相加在超过js数字精度时就不正确了

[yangchongduo]

也就是个位排在链表首部
(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
个位 在链表首部 不是应该 716 + 592

[AnranS]

var addTwoNumbers = function (l1, l2) {
 let dump = new ListNode();
 let p1 = l1, p2 = l2, current = dump;
 // 进位标识
 let curry = 0;
 while (p1 && p2) {
 let res = p1.val + p2.val + curry;
 curry = 0;
 if (res >= 10) {
 curry = 1;
 current.next = new ListNode(res % 10);
 } else {
 current.next = new ListNode(res);
 }
 current = current.next;
 p1 = p1.next;
 p2 = p2.next;
 }
 let rest = p1 === null ? p2 : p1;
 while (rest) {
 let res = rest.val + curry;
 curry = 0;
 if (res >= 10) {
 curry = 1;
 current.next = new ListNode(res % 10);
 } else {
 current.next = new ListNode(res);
 }
 rest = rest.next;
 current = current.next;
 }
 if (curry) current.next = new ListNode(curry);

 return dump.next;
};

[Anoi1018]

var addTwoNumbers = function(l1, l2) {
if(l1===null) return l2;
if(l2===null) return l1;
var carry = 0,sum=0,pre=new ListNode(0),p=pre,a,b;
while(l1 || l2){
a = l1===null? 0 : l1.val;
b = l2===null? 0 : l2.val;
sum = a+b+ carry;
var node= new ListNode(sum%10);
carry = (sum-sum%10)/10;
p.next = node;
p = node;
if(l1) l1= l1.next;
if(l2) l2= l2.next;
}

if(carry !== 0) p.next = new ListNode(carry);

return pre.next; 

};

[JohnApache]

反向求和的情况
利用了 递归回溯

const addTwoNumbers = (list1: Node, list2: Node) => {
 let multy = 0;
 const fn = (next1: Node | undefined, next2: Node | undefined) => {
 if (!next1 && !next2) {
 return multy > 0 ? new Node(multy) : undefined;
 }
 const element = (next1 ? next1.element : 0) + (next2 ? next2.element : 0) + multy;
 multy = Math.floor(element / 10);
 const node = new Node(element - multy * 10);
 node.next = fn(next1?.next, next2?.next);
 return node;
 };
 return fn(list1, list2);
};

正向求和

const addTwoNumbers2 = (list1: Node, list2: Node) => {
 let multy = 0;
 const fn = (next1: Node | undefined, next2: Node | undefined) => {
 if (!next1 && !next2) return undefined;
 const prevNode = fn(next1?.next, next2?.next);
 const element = (next1 ? next1.element : 0) + (next2 ? next2.element : 0) + multy;
 multy = Math.floor(element / 10);
 const node = new Node(element - multy * 10);
 node.next = prevNode;
 return node;
 };
 let result = fn(list1, list2);
 if (multy > 0) {
 const node = new Node(multy);
 node.next = result;
 result = node;
 }
 return result;
};