LeetCode #2 – Add Two Numbers

Problem Statement

1. Task


• 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.
• Add the two numbers and return the sum as a linked list (also in reverse order).


• Constraints (from the original problem):
  • Each linked list node stores a digit in the range [0, 9].
  • The two numbers do not contain leading zeros, except for the number 0 itself.


• Example:
  • l1 = [2, 4, 3] (represents 342)
  • l2 = [5, 6, 4] (represents 465)
  • Answer: [7, 0, 8] because 342 + 465 = 807.

Understanding the Linked List Representation

1. Reverse Order Digits


• Each list node holds a single digit, and the head of the list is the least significant digit.
• Example: 2 → 4 → 3 means the number 342, not 243.
• This is convenient because we can add numbers from right to left (like on paper) by starting at the list heads.


2. Different Lengths


• The two lists can have different lengths, e.g. [9, 9, 9] and [1].
• When one list is shorter, we treat missing digits as 0 during addition.

Core Idea: Simulate Column-wise Addition (O(n))

1. High-Level Idea


• We walk through both lists simultaneously, digit by digit.
• At each step, we:
  • Read the current digit from l1 (or 0 if l1 is null).
  • Read the current digit from l2 (or 0 if l2 is null).
  • Add them together with a carry from the previous step.
  • Create a new node whose value is the ones digit sum % 10.
  • Update carry = Math.floor(sum / 10).
• We use a dummy head node to simplify building the result list.
• If after processing all digits the carry is still non-zero, we append a final node.


2. Key Implementation Pattern



/**
 * Definition for singly-linked list.
 */
class ListNode {
    val: number;
    next: ListNode | null;

    constructor(val?: number, next?: ListNode | null) {
        this.val  = (val === undefined ? 0    : val);
        this.next = (next === undefined ? null : next);
    }
}

function addTwoNumbers(l1: ListNode | null, l2: ListNode | null): ListNode | null {
    const dummy = new ListNode(); // dummy head of result list
    let node = dummy;

    let carry = 0;

    // Traverse as long as there is at least one node left
    while (l1 || l2) {
        const sum =
            carry +
            (l1 ? l1.val : 0) +
            (l2 ? l2.val : 0);

        const digit = sum % 10;             // ones place
        carry = Math.floor(sum / 10);       // tens place (carry)

        node.next = new ListNode(digit);    // append new digit node
        node = node.next;

        l1 = l1?.next || null;              // move forward if possible
        l2 = l2?.next || null;
    }

    // If we still have a carry (e.g. 999 + 1 = 1000)
    if (carry !== 0) {
        node.next = new ListNode(carry);
    }

    return dummy.next; // real head of the result list
}

const solution1 = addTwoNumbers;

export {};

• dummy is a placeholder node that simplifies appending; the real result starts at dummy.next.
• The loop continues as long as either l1 or l2 is not null.
• We safely handle lists of different lengths by using (l1 ? l1.val : 0) and (l2 ? l2.val : 0).
• The final if (carry !== 0) handles cases like 9 + 1 = 10, where we need one extra digit node.

Example Walkthrough

• Input:
  • l1 = [2, 4, 3] ⇒ 342
  • l2 = [5, 6, 4] ⇒ 465

• Final result list: [7, 0, 8], which represents 807.

Complexity

• Time: We visit each node of l1 and l2 at most once ⇒ O(n), where n is the length of the longer list.
• Space: We create a new list to store the result, with at most n + 1 nodes (for the final carry) ⇒ O(n).