Problem Statement #

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each node contains a single digit. Your task is to add the two numbers and return the sum as a linked list.

Important constraints:

• The two numbers do not contain any leading zeros, except the number 0 itself
• Each node stores exactly one digit (0-9)
• The linked lists are in reverse order (least significant digit first)

Example:

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

Solution Overview #

This problem beautifully mimics how we learned to add numbers in elementary school. Remember stacking numbers vertically and adding column by column from right to left, carrying over when the sum exceeds 9? That’s exactly what we’re doing here, except the linked list structure already presents the digits in the convenient order we need (least significant first).

Code Implementation #

ListNode Definition #

// Given ListNode definition
function ListNode(val) {
    this.val = val;
    this.next = null;
}

Complete Solution #

var addTwoNumbers = function(l1, l2) {
    // Add numbers from two linked lists and return the sum as a linked list
    let carry = 0;
    let head = new ListNode(0);  // Dummy head node
    let curr = head;
    
    while (l1 || l2) {
        let l1val = 0;
        let l2val = 0;
        
        if (l1) {
            l1val = l1.val;
            l1 = l1.next;
        }
        
        if (l2) {
            l2val = l2.val;
            l2 = l2.next;
        }
        
        let thisDigit = l1val + l2val + carry;
        carry = 0;
        
        if (thisDigit >= 10) {
            thisDigit = thisDigit - 10;
            carry++;
        }
        
        curr.next = new ListNode(thisDigit);
        curr = curr.next;
    }
    
    // Fill in remaining carry digit
    if (carry > 0) {
        curr.next = new ListNode(carry);
    }
    
    // Return actual head (skip dummy node)
    return head.next;
};

Algorithm Approach #

The solution leverages the reverse order storage of digits in the linked lists. Since digits are stored from least significant to most significant, we can traverse both lists simultaneously and perform digit-by-digit addition just like manual arithmetic.

Key Insights #

1. Reverse Order Advantage: The least significant digit comes first, which is exactly the order we need for addition
2. Carry Propagation: When two digits sum to 10 or more, we carry 1 to the next position
3. Unequal Length Handling: One number might have more digits than the other, so we treat missing digits as 0
4. Final Carry: After processing both lists, we might still have a carry digit to append

Detailed Code Walkthrough #

Initialization Phase #

let carry = 0;
let head = new ListNode(0);
let curr = head;
while (l1 || l2) {

Variable Setup:

• carry: Stores the carry-over digit from addition (0 or 1). When 7 + 7 = 14, we store 4 and carry 1
• head: A dummy node that simplifies our linked list construction. This is a common pattern in linked list problems
• curr: A pointer tracking our current position in the result list. Declaring it here ensures proper scope throughout the function

Loop Condition: We continue as long as either l1 OR l2 has remaining nodes. This naturally handles lists of different lengths.

Value Extraction #

let l1val = 0;
let l2val = 0;

if (l1) {
    l1val = l1.val;
    l1 = l1.next;
}

if (l2) {
    l2val = l2.val;
    l2 = l2.next;
}

Why Initialize to Zero? If one list is shorter than the other, we’ve already reached its end (null). By defaulting to 0, we ensure that adding this value doesn’t affect the calculation—it’s like adding zeros to the front of a shorter number.

Advancement Logic: If a list node exists, we extract its value and move to the next node. These variables are scoped to each loop iteration and get re-declared fresh each time.

Digit Calculation and Carry Handling #

let thisDigit = l1val + l2val + carry;
carry = 0;

if (thisDigit >= 10) {
    thisDigit = thisDigit - 10;
    carry++;
}

curr.next = new ListNode(thisDigit);
curr = curr.next;

Addition Logic:

1. Sum the current digits from both lists plus any carry from the previous position
2. Reset carry to 0 (clean slate for this digit)
3. If the sum is 10 or greater, we extract the ones digit and set carry to 1

Example: If l1val = 7, l2val = 8, and carry = 1:

• thisDigit = 7 + 8 + 1 = 16
• Since 16 ≥ 10, we set thisDigit = 6 and carry = 1

Result Construction: We create a new node with the calculated digit and append it to our result list. Then we advance our pointer to this new tail node, ready for the next iteration.

Finalizing the Result #

// Fill in remaining carry digit
if (carry > 0) {
    curr.next = new ListNode(carry);
}

// Return actual head (skip dummy node)
return head.next;

Final Carry Check: After the main loop completes, we might still have a carry digit. For example, when adding 999 + 1, we get 1000, requiring an extra digit at the end.

Dummy Node Pattern: We return head.next instead of head because our first node is a dummy placeholder. This pattern simplifies our loop logic—we always append to curr.next without special-casing the first real node.

Complexity Analysis #

Time Complexity: O(max(m, n)), where m and n are the lengths of the two linked lists. We traverse each list exactly once.

Space Complexity: O(max(m, n)). The result list will have at most max(m, n) + 1 nodes (the extra node accounts for a final carry).

Edge Cases Handled #

1. Different length lists: The shorter list is treated as having trailing zeros
2. Final carry: Numbers like 999 + 1 = 1000 require an extra node
3. Zero values: Works correctly when one or both inputs are [0]

Alternative Approaches #

While this solution is optimal, you could also:

• Convert to integers: Extract digits, form integers, add them, convert back. However, this fails for very large numbers exceeding JavaScript’s number precision
• Recursive solution: Implement the same logic recursively, though it offers no advantage and uses more stack space

This iterative approach with a dummy head node is the industry-standard solution, balancing clarity, efficiency, and correctness.

Conclusion #

This problem elegantly demonstrates how data structure choice (reverse order linked list) can simplify algorithm implementation. The solution mirrors elementary arithmetic, showing that sometimes the best algorithms are inspired by the simplest real-world methods we learned as children.