W10D5.js

//Write an algorithm which will sum two numbers stored in linked lists, where
//each node contains a single digit of the number.

//Assuming that the head of the list is the least significant digit, and that
//each list contains a minimum of one node (which may be zero).
var BASE = 10; //Each digit in the linked list is smaller than this.
function add_numbers(list1, list2) {
	var carry = 0;
	var ret, tail = null;
	while (list1 || list2 || carry) {
		var sum = (list1 && list1.digit) + (list2 && list2.digit) + carry;
		if (carry = sum >= BASE) sum -= BASE;
		var node = {digit: sum, next: null};
		if (!tail) ret = node;
		else tail.next = node;
		tail = node;
		if (list1) list1 = list1.next;
		if (list2) list2 = list2.next;
	}
	return ret;
}

function make_number(str) {
	var ret = null;
	for (var i = 0; i < str.length; ++i)
		ret = {digit: str.charCodeAt(i) - 48, next: ret}
	return ret;
}

function stringify(num) {
	var ret = "";
	while (num) {
		ret = num.digit + ret;
		num = num.next;
	}
	return ret;
}

//Demo function: add two integers represented as strings
function add_strings(s1, s2) {
	return stringify(add_numbers(make_number(s1), make_number(s2)));
}

console.log(add_strings("12345", "678"));
console.log(add_strings("999999999999999999999999999999999999999", "1"));
console.log(add_strings("13458924560", "3458929034580234"));
console.log(add_strings("1", "1"));

/*
Note that the original problem description merely said "digits", leaving the
base unspecified. As an interview question, it can be safely assumed that this
means decimal digits, but the algorithm is quite happy to work with any other
base. (The demo functions that convert to and from strings won't work with any
other base, though.) One very effective base is 4294967296, using one 32-bit
integer in each node; if you're worried about signed integer support, use base
2147483648 instead. This is one way to achieve bignum support. Addition and
subtraction are fairly easy; multiplication is rather more complicated, and
division is pretty hard. But all are possible, and without loss of precision.

(Note that this function assumes nonnegative numbers. Supporting all integers
is left as an exercise for the reader.)
*/