How to sum two linked lists where each node represents a digit

Here is one way to sum two linked lists where each node represents a digit:

sumListsTry in REPL
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// sum lists where digits are in reverse order
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; // second digit of num
// Recurse
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;
};
// sum lists where digits are stored in forward order
function PartialSum() {
this.sum = null;
this.carry = 0;
}
function sumForward(list1, list2, carry) {
const len1 = getLength(list1);
const len2 = getLength(list2);
// Pad shorter list with zeros
if (len1 < len2) {
list1 = padList(list1, len2 - len1);
} else {
list2 = padList(list2, len1 - len2);
}
const sum = addListsHelper(list1, list2);
// if value left over, insert at front of list, otherwise just return linked list
if (sum.carry === 0) {
return sum.sum;
} else {
const result = insertBefore(sum.sum, sum.carry);
return result;
}
}
// helper for adding the lists
function addListsHelper(list1, list2) {
if (!list1 && !list2) {
const sum = new PartialSum();
return sum;
}
// add smaller digits recursively
const sum = addListsHelper(list1.next, list2.next);
// add carry to current data
const value = sum.carry + list1.data + list2.data;
// insert sum of current digits
const fullResult = insertBefore(sum.sum, value % 10);
// Return sum so far
sum.sum = fullResult;
sum.carry = Math.floor(value / 10);
return sum;
}
// helper function used to get the length of a linked list
function getLength(list) {
let total = 0;
let current = list;
while (current) {
total++;
current = current.next;
}
return total;
}
// helper function used to make list lengths equal
function padList(list, n) {
let head = list;
for (let i = 0; i < n; i++) {
head = insertBefore(head, 0);
}
return head;
}
// helper function to insert something in front of a linked list
function insertBefore(target, data) {
const node = new Node(data);
if (target) {
node.next = target;
}
return node;
}

Tests can be found at REPL.it