Add Two Numbers medium

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.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

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]

Steps

1. Initialization: Create a dummy node head to simplify the handling of the first node of the result list. Initialize a carry variable to 0. Set a current node currentNode to head.

2. Iteration: Iterate while either l1 or l2 is not null, or the carry is not 0.

3. Node Value Calculation: Get the values of the current nodes in l1 and l2 (or 0 if a list is exhausted). Add these values and the carry to get the sum.

4. Digit Extraction and Carry Update: Extract the last digit of the sum (using the modulo operator %) and create a new node with this digit. Update carry by integer dividing the sum by 10.

5. Linking and Movement: Link the new node to the currentNode, and move currentNode to the new node. Advance l1 and l2 to the next nodes if they are not null.

6. Result: After the loop, return the next node after head (the actual head of the result list).

Explanation

The algorithm simulates manual addition of numbers. We iterate through the lists, adding digits along with any carry from the previous addition. The modulo operator helps us extract the last digit (the units place), while integer division updates the carry for the next addition. The dummy node simplifies the handling of the first node's creation.

Code

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 head = new ListNode(0); // Dummy node
    let currentNode = head;
    let carry = 0;

    while (l1 !== null || l2 !== null || carry !== 0) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        const sum = val1 + val2 + carry;

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

        currentNode.next = new ListNode(digit);
        currentNode = currentNode.next;

        l1 = l1 ? l1.next : null;
        l2 = l2 ? l2.next : null;
    }

    return head.next;
}


// Example usage:
const l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
const l2 = new ListNode(5, new ListNode(6, new ListNode(4)));

const result = addTwoNumbers(l1, l2);

let current = result;
let output = "";
while(current){
    output += current.val + " ";
    current = current.next;
}
console.log(output); // Output: 7 0 8 

Complexity

• Time Complexity: O(max(m, n)), where 'm' and 'n' are the lengths of the input linked lists. We iterate through the lists at most once.
• Space Complexity: O(max(m, n)), in the worst case, the resulting linked list has a length equal to the maximum length of the input lists plus one (for the carry). This is because we are creating new nodes for the result list.