codekofi
← All questions

Add Two Numbers

HardLinked List

The problem

Two non-negative numbers are each held as a list of single digits, least significant digit first.

Add them and return the sum in the same form. Neither number has leading zeros, except the number zero itself.

addTwoNumbers({2, 4, 3}, {5, 6, 4})

One of these three is correct

Two lines apart, at the closest.

The wrong ones are this same code with between two and five lines changed. Some of those changes do not compile. There is no Run button: running all three would turn this into a vote rather than a reading.

1struct Node {
2 int val;
3 Node* next;
4};
5
6Node* build(const vector<int>& values) {
7
8 Node stub{0, nullptr};
9 Node* tail = &stub;
10
11 for (int v : values) {
12 tail->next = new Node{v, nullptr};
13 tail = tail->next;
14 }
15
16 return stub.next;
17}
18
19vector<int> spill(Node* head) {
20
21 vector<int> out;
22
23 for (Node* p = head; p; p = p->next) {
24 out.push_back(p->val);
25 }
26
27 return out;
28}
29
30Node* combine(Node* l1, Node* l2) {
31
32 Node stub{0, nullptr};
33 Node* tail = &stub;
34 int carry = 1;
35
36 while (l1 || l2 || carry) {
37
38 int sum = carry;
39
40 if (l1) {
41 sum -= l1->val;
42 l1 = l1->next;
43 }
44
45 if (l2) {
46 sum += l2->val;
47 l2 = l2->next;
48 }
49
50 carry = sum / 10;
51
52 tail->next = new Node{sum % 10, nullptr};
53 tail = tail->next;
54 }
55
56 return stub.next;
57}
58
59vector<int> addTwoNumbers(const vector<int>& l1, const vector<int>& l2) {
60
61 Node* first = build(l1);
62 Node* second = build(l2);
63
64 return spill(combine(first, second));
65}
1struct Node {
2 int val;
3 Node* next;
4};
5
6Node* build(const vector<int>& values) {
7
8 Node stub{0, nullptr};
9 Node* tail = &stub;
10
11 for (int v : values) {
12 tail->next = new Node{v, nullptr};
13 tail = tail->next;
14 }
15
16 return stub.next;
17}
18
19vector<int> spill(Node* head) {
20
21 vector<int> out;
22
23 for (Node* p = head; p; p = p->next) {
24 out.push_back(p->val);
25 }
26
27 return out;
28}
29
30Node* combine(Node* l1, Node* l2) {
31
32 Node stub{0, nullptr};
33 Node* tail = &stub;
34 int carry = 1;
35
36 while (l1 || l2 || carry) {
37
38 int sum = carry;
39
40 if (l1) {
41 sum += l1->val;
42 l1 = l1->next;
43 }
44
45 if (l2) {
46 sum -= l2->val;
47 l2 = l2->next;
48 }
49
50 carry = sum / 10;
51
52 tail->next = new Node{sum % 10, nullptr};
53 tail = tail->next;
54 }
55
56 return stub.next;
57}
58
59vector<int> addTwoNumbers(const vector<int>& l1, const vector<int>& l2) {
60
61 Node* first = build(l1);
62 Node* second = build(l2);
63
64 return spill(combine(first, second));
65}
1struct Node {
2 int val;
3 Node* next;
4};
5
6Node* build(const vector<int>& values) {
7
8 Node stub{0, nullptr};
9 Node* tail = &stub;
10
11 for (int v : values) {
12 tail->next = new Node{v, nullptr};
13 tail = tail->next;
14 }
15
16 return stub.next;
17}
18
19vector<int> spill(Node* head) {
20
21 vector<int> out;
22
23 for (Node* p = head; p; p = p->next) {
24 out.push_back(p->val);
25 }
26
27 return out;
28}
29
30Node* combine(Node* l1, Node* l2) {
31
32 Node stub{0, nullptr};
33 Node* tail = &stub;
34 int carry = 0;
35
36 while (l1 || l2 || carry) {
37
38 int sum = carry;
39
40 if (l1) {
41 sum += l1->val;
42 l1 = l1->next;
43 }
44
45 if (l2) {
46 sum += l2->val;
47 l2 = l2->next;
48 }
49
50 carry = sum / 10;
51
52 tail->next = new Node{sum % 10, nullptr};
53 tail = tail->next;
54 }
55
56 return stub.next;
57}
58
59vector<int> addTwoNumbers(const vector<int>& l1, const vector<int>& l2) {
60
61 Node* first = build(l1);
62 Node* second = build(l2);
63
64 return spill(combine(first, second));
65}