DAY 94 - Add Two Numbers

Let's solve one of the most famous leetcode questions today which is about adding two numbers in a linked list.

Analyzing Add Two Numbers" 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.

Understanding the Problem

Before diving into the code, let's break down the problem and understand what's expected:

• You're given two linked lists, l1 and l2, where each node contains a digit.

• The digits are stored in reverse order. That means the 1's digit is at the head of the list, followed by the 10's digit, and so on.

• Your task is to add these two numbers and return the result as a linked list.

The Approach

To solve this problem, we can use a simple iterative approach that resembles how we manually add numbers. Here's the intuition behind the approach:

1. Initialize Variables: We start by initializing some variables. We'll maintain two pointers, temp1 and temp2, to traverse l1 and l2, respectively. We also initialize a carry variable to handle carryovers during addition.

2. Initialize the Result List: We create a new linked list called ans to store the result. Additionally, we keep a pointer called start to the current node in the ans list.

3. Iterate Through the Lists: We use a while loop that continues until both temp1 and temp2 reach the end of their respective lists. In each iteration, we perform the following steps:

• Extract the values val1 and val2 from the current nodes temp1 and temp2, respectively. If either of the lists has reached its end, we consider the value as 0.

• Calculate the sum of val1, val2, and the carry from the previous step.

• Update the current node in the result list (start) with the last digit of the sum (sum % 10) and calculate the carry for the next iteration (carry = sum / 10).

• Move temp1 and temp2 to their respective next nodes, if available.

• If there are more digits in either l1 or l2, or if there's a carry from the last addition, we create a new node in the result list and move the start pointer to this new node.

1. Handle Any Remaining Carry: After the loop, if there's still a carry (which could happen if the last addition results in a carry), we create one final node in the result list to accommodate the carry.

2. Return the Result: Finally, we return the ans linked list, which represents the sum of the two input numbers.

Code:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        int carry = 0;
        ListNode* temp1 = l1;
        ListNode* temp2 = l2;
        ListNode* ans = new ListNode();
        ListNode* start = ans;

        while (temp1 || temp2) {
            int val1 = (temp1) ? temp1->val : 0;
            int val2 = (temp2) ? temp2->val : 0;

            int sum = val1 + val2 + carry;

            start->val = sum % 10;
            carry = sum / 10;

            if (temp1) temp1 = temp1->next;
            if (temp2) temp2 = temp2->next;

            if (temp1 || temp2 || carry > 0) {
                start->next = new ListNode();
                start = start->next;
            }
        }

        if (carry > 0) {
            start->val = carry;
        }

        return ans;
    }
};

Time and Space Complexity

Let's analyze the time and space complexity of our solution:

• Time Complexity: The algorithm makes a single pass through both input lists, so its time complexity is O(max(N, M)), where N and M are the lengths of l1 and l2, respectively.

• Space Complexity: We create a new linked list to store the result, which takes O(N) space where N is the greater value.