Add Two Numbers – LeetCode Solution

Problem

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:

Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:

Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9] Output: [8,9,9,9,0,0,0,1]

Check out the problem here – Add Two Numbers – LeetCode

Solution

As the linked list is in reverse order starting with the least significant digit, we can iterate through the list doing digit wise addition and pass on the carry to next digit in the list. To store the result, we need to construct a new linked list to store the resultant sum of the digits.

Corner Cases:

The list can be of different sizes. The condition of the loop should be in a way that the loop continues if either of the list is not empty.

Also, there can be a carry in the last addition of digits. We need to be sure to add that carry into the list we have for storing the resultant sum of digits.

1. We create a head node to store the resultant list of digits for the sum.
2. We create a tail node and store the head to the tail, as we do not have any digits in the list. This pointer is used to keep track of the last node in the linked list.
3. We initialize a variable to store the carry.
4. We start a loop with condition that either one of the lists should have a value or the carry should be one. This ensures that the loop continues when the list is of unequal length or if there is a carry in the last addition of digits.
5. Inside the loop, we only take the value from list that is contains a valid value. We add them together with the carry.
6. We check if the resulting addition is greater than or equal to 10. If the condition holds true, we set the carry, else we clear the carry.
7. We create a new node to store the calculated digit.
8. We attach the node to the tail node and update the tail node pointer to point the new node.
9. We move to the next node in the pointers l1 and l2 if they exist, else we set them to null.
10. We return the result nodes.

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        
        /*Create two nodes, one for head of list and one for tail of list */
        ListNode* head_node = new ListNode(0);
        ListNode* tail_node = head_node;
        int carry = 0;

        while (l1 != nullptr || l2 != nullptr || carry != 0) {
            
            int val1 = (l1 != nullptr) ? l1->val : 0;
            int val2 = (l2 != nullptr) ? l2->val : 0;

            int sum = val1 + val2 + carry;
            if(sum >=10 )
            {
                sum = sum -10;
                carry = 1;
            }else
            {
                carry = 0;
            }

            ListNode* temp_node = new ListNode(sum);
            tail_node->next = temp_node;
            tail_node = tail_node->next;

            l1 = (l1 != nullptr) ? l1->next : nullptr;
            l2 = (l2 != nullptr) ? l2->next : nullptr;
        }

        ListNode* result = head_node->next;
        delete head_node;
        return result;
    }
};

Please comment below if you are aware of any optimizations to the above code. As a follow up question, think of a solution when the digits in the linked list are stored in a non-reversed order.