2. Add Two Numbers

📝 Problem Details

• Title: 2. Add Two Numbers
• Link: https://leetcode.com/problems/add-two-numbers/
• Difficulty: Medium
• Tags/Categories: Linked-List Math Recursion

💭What Were My Initial Thoughts?

- the reverse order is beneficial and should not impact the way we approach the problem
- there are lots of edge cases
	- non-negative numbers
	- adding two numbers can result in a val more than 1 digit
	- the addition of two numbers at the end of the list will result in a new node being created
	- lists can be of differing lengths

🤔What Did I Struggle With?

- took me longer than it should have to start coding

💡 Explanation of Solution

create a dummy node that will act as the head of the new list we return
create a current node that points to head
create a carry integer variable to hold values from the previous sum 

iterate through both l1 and l2 

⌛ Complexity Analysis

O(n + m) TC since we are iterating through the entire length of both lists

💻 Implementation of Solution

class Solution {
 
public:
 
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode(0);
        ListNode* current = dummy;
        int carry = 0;
 
        while(l1 != nullptr || l2 != nullptr) {
            int sum = carry;
 
            if(l1 != nullptr) {
                sum += l1->val;
                l1 = l1->next;
            }
 
            if(l2 != nullptr) {
                sum += l2->val;
                l2 = l2->next;
            }
 
            carry = sum / 10;
            current->next = new ListNode(sum % 10);
            current = current->next;
        }
 
        if(carry > 0) {
            current->next = new ListNode(carry);
        }
        return dummy->next;
    }
 
};