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;
}