function sum(list1, list2, carry) {
if (!list1 && !list2 && carry === 0) {
return null;
}
const result = new Node();
let value = !carry ? 0 : carry;
if (list1) {
value += list1.data;
}
if (list2) {
value += list2.data;
}
result.data = value % 10;
if (list1 || list2) {
const more = sum(!list1 ? null : list1.next, !list2 ? null : list2.next, value >= 10 ? 1 : 0);
result.next = more;
}
return result;
}
function Node(data) {
this.next = null;
this.data = data;
}
Node.prototype.addToTail = function(data) {
const end = new Node(data);
let current = this;
while (current.next !== null) {
current = current.next;
}
current.next = end;
return end;
};
function PartialSum() {
this.sum = null;
this.carry = 0;
}
function sumForward(list1, list2, carry) {
const len1 = getLength(list1);
const len2 = getLength(list2);
if (len1 < len2) {
list1 = padList(list1, len2 - len1);
} else {
list2 = padList(list2, len1 - len2);
}
const sum = addListsHelper(list1, list2);
if (sum.carry === 0) {
return sum.sum;
} else {
const result = insertBefore(sum.sum, sum.carry);
return result;
}
}
function addListsHelper(list1, list2) {
if (!list1 && !list2) {
const sum = new PartialSum();
return sum;
}
const sum = addListsHelper(list1.next, list2.next);
const value = sum.carry + list1.data + list2.data;
const fullResult = insertBefore(sum.sum, value % 10);
sum.sum = fullResult;
sum.carry = Math.floor(value / 10);
return sum;
}
function getLength(list) {
let total = 0;
let current = list;
while (current) {
total++;
current = current.next;
}
return total;
}
function padList(list, n) {
let head = list;
for (let i = 0; i < n; i++) {
head = insertBefore(head, 0);
}
return head;
}
function insertBefore(target, data) {
const node = new Node(data);
if (target) {
node.next = target;
}
return node;
}