快手算法：链表求和

[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;
};