Add Two Numbers | Leetcode 2 | Optimal Solution

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.

Here’s the [Problem Link] to begin with.

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]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].
• 0 <= Node.val <= 9
• It is guaranteed that the list represents a number that does not have leading zeros.

Solution: Optimal Approach (Digit by Digit Addition)

Intuition

Think of this like adding two numbers on paper, but instead of writing digits left-to-right, we’re adding them right-to-left (which is actually easier!). Since the linked lists already store digits in reverse order, we can directly add corresponding digits from both lists, handle any carry, and build our result list as we go. It’s like having two people read out digits from the end of two numbers, and you write down the sum digit by digit!

Detailed Approach

1. Create Result Structure: Use a dummy node to simplify the result list construction
2. Initialize Variables: Keep track of carry and current position in result list
3. Process Both Lists: While either list has nodes or we have a carry to process
4. Add Digits: Sum the current digits from both lists plus any carry
5. Handle Carry: If sum is greater than 9, set carry for next iteration
6. Create Result Node: Add the current digit (sum % 10) to result list
7. Move Forward: Advance pointers in both input lists and result list

Code

class Solution:
    def addTwoNumbers(
        self, l1: Optional[ListNode], l2: Optional[ListNode]
    ) -> Optional[ListNode]:
        result = ListNode(0)     # Dummy node to simplify list construction
        temp = result            # Pointer to build result list
        carry = 0               # Variable to handle carry from previous addition
        
        # Continue while either list has nodes or we have carry
        while (l1 != None and l2 != None) or carry:
            total = 0           # Sum of current digits plus carry
            
            # Add digit from first list if available
            if l1 != None:
                total += l1.val
                l1 = l1.next    # Move to next node
            
            # Add digit from second list if available
            if l2 != None:
                total += l2.val
                l2 = l2.next    # Move to next node
            
            total += carry      # Add carry from previous iteration
            
            # Calculate carry for next iteration
            if total > 9:
                carry = 1
            else:
                carry = 0
            
            # Create new node with current digit and add to result
            temp.next = ListNode(total % 10)
            temp = temp.next    # Move result pointer forward
        
        return result.next      # Return actual result (skip dummy node)

Code Explanation

This solution simulates the manual addition process we learned in school. We use a dummy node to make list construction easier – this way we don’t need to handle the special case of creating the first node. We process both lists simultaneously, adding corresponding digits along with any carry from the previous addition. The key insight is that we continue the loop even after one or both lists are exhausted, as long as we have a carry to process. We use modulo arithmetic to get the current digit (total % 10) and integer division logic to determine the carry.

Dry Run

Let’s trace through: l1 = (represents 342), l2 = (represents 465)

Initial Setup:

• result = dummy node, temp = result, carry = 0
• l1 points to 2, l2 points to 5

Iteration 1:

• total = 2 + 5 + 0 = 7
• carry = 0 (since 7 ≤ 9)
• Create node with value 7: result -> 7
• Move: l1 to 4, l2 to 6, temp to node 7

Iteration 2:

• total = 4 + 6 + 0 = 10
• carry = 1 (since 10 > 9)
• Create node with value 0: result -> 7 -> 0
• Move: l1 to 3, l2 to 4, temp to node 0

Iteration 3:

• total = 3 + 4 + 1 = 8
• carry = 0 (since 8 ≤ 9)
• Create node with value 8: result -> 7 -> 0 -> 8
• Move: l1 to None, l2 to None, temp to node 8

Final Check:

• Both lists exhausted and carry = 0, so loop ends
• Return result.next:

Result: “ represents 807, which is 342 + 465 ✓

Time and Space Complexity

• Time Complexity: O(max(m, n)) – We process each digit from both lists once, where m and n are the lengths of the lists
• Space Complexity: O(max(m, n)) – The result list will have at most max(m, n) + 1 nodes

Simplifying It

This approach is like being a calculator that works digit by digit from right to left. You look at the rightmost digits of both numbers, add them up (plus any carry from before), write down the result digit, and remember if you need to carry anything to the next position. Since the linked lists are already in reverse order, this process becomes very natural and straightforward.

Key Insights

Why the dummy node helps:
Using a dummy node eliminates the need to handle the special case of creating the first result node. We can always do temp.next = new_node instead of checking if we’re creating the first node.

Why we continue with carry:
Even when both input lists are exhausted, we might still have a carry to process. For example, adding 99 + 1 would require adding an extra digit at the front.

Why modulo arithmetic works:
total % 10 gives us the digit to store in the current position, while total > 9 tells us if we need to carry 1 to the next position.

Summary

This optimal solution efficiently handles the addition in a single pass while properly managing carries. The key insight is that since the digits are already in reverse order, we can directly simulate the manual addition process without any preprocessing.

This problem beautifully demonstrates how understanding the problem’s natural structure (digits in reverse order) can lead to an elegant solution. The algorithm is both intuitive and efficient, making it a great example of how to handle linked list manipulation with mathematical operations!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.