Name: Add Two Numbers
Difficulty: Medium
Description: Add two numbers stored in reverse in a linked list
Example:
Input: l1 = [2,4,3], l2 = [5,6,4] Output: [7,0,8] Explanation: 342 + 465 = 807. Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]
Initially when solving this problem, I first made sure the lists were the same size by appending zeros to the smaller list. So considering the second example above, my lists would look like this:
l1 = [9, 9, 9, 9, 9, 9, 9]; l2 = [9, 9, 9, 9, 0, 0, 0];
That symmetry sat well with my brain and simplified the solution: Loop from start to end adding l1’s digit to l2’s digit, and apply any carry overs. Once I got it working, I then dropped the padding and just supplied the zero on demand. That made the solution nearly 35% faster:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if (l1 == nullptr && l2 == nullptr) return nullptr;
if (l1 == nullptr) return l2;
if (l2 == nullptr) return l1;
int carry = 0;
auto result = new ListNode();
ListNode * node = nullptr;
int a, b;
while(l1 != nullptr || l2 != nullptr) {
if (node == nullptr) {
node = result;
} else {
node = node->next = new ListNode();
}
if (l1 == nullptr) {
a = 0;
} else {
a = l1->val;
l1 = l1->next;
}
if (l2 == nullptr) {
b = 0;
} else {
b = l2->val;
l2 = l2->next;
}
int sum = a + b + carry;
if (sum < 10) {
node->val = sum;
carry = 0;
} else {
node->val = sum % 10;
carry = 1;
}
}
if (carry > 0) {
node->next = new ListNode(carry);
}
return result;
}