LeetCode Problem #2: Add Two Numbers - Explanation and Solutions in Python and JavaScript

Introduction

The Add Two Numbers problem is a classic linked list problem frequently asked in coding interviews. It tests your understanding of linked lists, pointer manipulation, and edge cases. In this post, we'll break down the problem, explain the optimal approach, and provide solutions in both Python and JavaScript.

Problem Statement

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.

Example:

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

Approach

The problem can be solved by simulating the addition process digit by digit, starting from the head of both linked lists. We maintain a carry to handle sums greater than 9. The steps are as follows:

1. Initialize a dummy node to build the result linked list.
2. Traverse both linked lists, adding corresponding digits along with the carry.
3. Store the sum's unit digit in the result linked list and update the carry.
4. If one list is longer than the other, continue adding the remaining digits along with the carry.
5. If there's a carry left after the traversal, add it to the result.

Solution in Python

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def addTwoNumbers(l1, l2):
    dummy = ListNode()
    current = dummy
    carry = 0

    while l1 or l2 or carry:
        val1 = l1.val if l1 else 0
        val2 = l2.val if l2 else 0

        total = val1 + val2 + carry
        carry = total // 10
        current.next = ListNode(total % 10)
        current = current.next

        if l1:
            l1 = l1.next
        if l2:
            l2 = l2.next

    return dummy.next
        

Explanation: We use a dummy node to simplify the creation of the result linked list. We iterate through both linked lists, add the corresponding digits along with the carry, and build the result linked list.

Solution in JavaScript

// Definition for singly-linked list.
function ListNode(val, next) {
    this.val = (val === undefined ? 0 : val);
    this.next = (next === undefined ? null : next);
}

function addTwoNumbers(l1, l2) {
    let dummy = new ListNode();
    let current = dummy;
    let carry = 0;

    while (l1 || l2 || carry) {
        let val1 = l1 ? l1.val : 0;
        let val2 = l2 ? l2.val : 0;

        let total = val1 + val2 + carry;
        carry = Math.floor(total / 10);
        current.next = new ListNode(total % 10);
        current = current.next;

        if (l1) l1 = l1.next;
        if (l2) l2 = l2.next;
    }

    return dummy.next;
}
        

Explanation: Similar to the Python solution, we use a dummy node and iterate through both linked lists, adding digits and handling the carry to build the result linked list.

Time and Space Complexity

Time Complexity: O(max(n, m)) - Where n and m are the lengths of the two linked lists.
Space Complexity: O(max(n, m)) - The length of the result linked list.

Edge Cases

• One list is longer than the other.
• Both lists are of the same length but have a carry at the end.
• One or both lists are empty (though the problem states they are non-empty).

Conclusion

The Add Two Numbers problem is an excellent way to practice linked list manipulation and handling edge cases. By understanding this approach, you can solve similar problems like Multiply Two Numbers or Add Two Numbers II. Try solving it on your own and explore related problems on LeetCode!