Day 07/90: Adding Two Numbers Represented by Linked Lists in TypeScript/JavaScript

Introduction When numbers are represented as linked lists where each digit is stored in reverse order, adding them requires careful traversal and carry management. Today, we'll solve LeetCode Problem 2 ("Add Two Numbers") efficiently in TypeScript/JavaScript. The Problem Given two non-empty linked lists representing two non-negative integers (with digits stored in reverse order), add the two numbers and return the sum as a linked list. Example: Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Explanation: 342 + 465 = 807 The Optimal Solution function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null { let dummy = new ListNode(0); let current = dummy; let carry = 0; while (l1 || l2 || carry) { const x = l1 ? l1.val : 0; const y = l2 ? l2.val : 0; const sum = x + y + carry; carry = Math.floor(sum / 10); current.next = new ListNode(sum % 10); current = current.next; if (l1) l1 = l1.next; if (l2) l2 = l2.next; } return dummy.next; }; This solution is: ✅ Efficient - O(max(n,m)) time complexity ✅ Clean - Handles all cases uniformly ✅ Memory-friendly - O(max(n,m)) space complexity How It Works Dummy Node: Simplifies edge cases by providing an initial node Carry Propagation: Tracks overflow between digit places Flexible While Condition: Continues until both lists and carry are exhausted Null Handling: Safely accesses values using ternary operators Alternative Approaches Recursive Solution function addTwoNumbers(l1: ListNode | null, l2: ListNode | null, carry = 0): ListNode | null { if (!l1 && !l2 && !carry) return null; const sum = (l1?.val || 0) + (l2?.val || 0) + carry; return new ListNode( sum % 10, addTwoNumbers(l1?.next || null, l2?.next || null, Math.floor(sum / 10)) ); } Pros: More declarative style No dummy node needed Cons: Potential stack overflow for very long lists Slightly less efficient Convert-and-Add Approach: function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null { const num1 = listToNum(l1); const num2 = listToNum(l2); return numToList(num1 + num2); } function listToNum(node: ListNode | null): number { let num = 0; let place = 1; while (node) { num += node.val * place; place *= 10; node = node.next; } return num; } function numToList(num: number): ListNode | null { if (num === 0) return new ListNode(0); let dummy = new ListNode(0); let current = dummy; while (num > 0) { current.next = new ListNode(num % 10); current = current.next; num = Math.floor(num / 10); } return dummy.next; } Pros: Conceptually simple Easy to understand Cons: Fails with very large numbers (JavaScript number precision limits) Inefficient for long lists Edge Cases to Consider Lists of different lengths Final carry (e.g., 5 + 5 = 10) Zero values Single-digit lists Large numbers (but within JavaScript safe integer range) Performance Considerations The optimal solution: Processes each node exactly once Uses constant extra space (just the carry) Minimizes memory allocations Conclusion The dummy node approach provides the best combination of:

Apr 29, 2025 - 15:52

Day 07/90: Adding Two Numbers Represented by Linked Lists in TypeScript/JavaScript

Introduction

When numbers are represented as linked lists where each digit is stored in reverse order, adding them requires careful traversal and carry management. Today, we'll solve LeetCode Problem 2 ("Add Two Numbers") efficiently in TypeScript/JavaScript.

The Problem
Given two non-empty linked lists representing two non-negative integers (with digits stored in reverse order), add the two numbers and return the sum as a linked list.

Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807

The Optimal Solution

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

    while (l1 || l2 || carry) {
        const x = l1 ? l1.val : 0;
        const y = l2 ? l2.val : 0;
        const sum = x + y + carry;

        carry = Math.floor(sum / 10);
        current.next = new ListNode(sum % 10);
        current = current.next;

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

    return dummy.next;
};

This solution is:
✅ Efficient - O(max(n,m)) time complexity
✅ Clean - Handles all cases uniformly
✅ Memory-friendly - O(max(n,m)) space complexity

How It Works
Dummy Node: Simplifies edge cases by providing an initial node

Carry Propagation: Tracks overflow between digit places

Flexible While Condition: Continues until both lists and carry are exhausted

Null Handling: Safely accesses values using ternary operators

Alternative Approaches

Recursive Solution

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null, carry = 0): ListNode | null {
    if (!l1 && !l2 && !carry) return null;

    const sum = (l1?.val || 0) + (l2?.val || 0) + carry;
    return new ListNode(
        sum % 10,
        addTwoNumbers(l1?.next || null, l2?.next || null, Math.floor(sum / 10))
    );
}

Pros:

More declarative style

No dummy node needed

Cons:

Potential stack overflow for very long lists

Slightly less efficient

Convert-and-Add Approach:

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const num1 = listToNum(l1);
    const num2 = listToNum(l2);
    return numToList(num1 + num2);
}

function listToNum(node: ListNode | null): number {
    let num = 0;
    let place = 1;
    while (node) {
        num += node.val * place;
        place *= 10;
        node = node.next;
    }
    return num;
}

function numToList(num: number): ListNode | null {
    if (num === 0) return new ListNode(0);

    let dummy = new ListNode(0);
    let current = dummy;

    while (num > 0) {
        current.next = new ListNode(num % 10);
        current = current.next;
        num = Math.floor(num / 10);
    }

    return dummy.next;
}

Pros:

Conceptually simple

Easy to understand

Cons:

Fails with very large numbers (JavaScript number precision limits)

Inefficient for long lists

Edge Cases to Consider
Lists of different lengths

Final carry (e.g., 5 + 5 = 10)

Zero values

Single-digit lists

Large numbers (but within JavaScript safe integer range)

Performance Considerations
The optimal solution: