Add Two Numbers

Loading...LeetCode

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]

Constraints:

• The number of nodes in each linked list is in the range [1, 100].

• 0 <= Node.val <= 9

• It is guaranteed that the list represents a number that does not have leading zeros.

Solution:

To solve this problem, you can traverse both linked lists simultaneously, summing up the corresponding digits at each position. Keep track of any carry that might occur. Create a new linked list to store the result.

Here's the JavaScript implementation:

class ListNode {
    constructor(val = 0, next = null) {
        this.val = val;
        this.next = next;
    }
}

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

    while (l1 || l2) {
        const val1 = l1 ? l1.val : 0;
        const val2 = l2 ? l2.val : 0;
        const sum = val1 + val2 + 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;
    }

    if (carry > 0) {
        current.next = new ListNode(carry);
    }

    return dummyHead.next;
}

// Helper function to create a linked list from an array
function createLinkedListFromArray(arr) {
    let head = new ListNode(arr[0]);
    let current = head;
    for (let i = 1; i < arr.length; i++) {
        current.next = new ListNode(arr[i]);
        current = current.next;
    }
    return head;
}

// Helper function to convert a linked list to array
function linkedListToArray(head) {
    const result = [];
    let current = head;
    while (current) {
        result.push(current.val);
        current = current.next;
    }
    return result;
}

// Test cases
const l1 = createLinkedListFromArray([2, 4, 3]);
const l2 = createLinkedListFromArray([5, 6, 4]);
const result1 = addTwoNumbers(l1, l2);
console.log(linkedListToArray(result1)); // Output: [7, 0, 8]

const l3 = createLinkedListFromArray([0]);
const l4 = createLinkedListFromArray([0]);
const result2 = addTwoNumbers(l3, l4);
console.log(linkedListToArray(result2)); // Output: [0]

const l5 = createLinkedListFromArray([9, 9, 9, 9, 9, 9, 9]);
const l6 = createLinkedListFromArray([9, 9, 9, 9]);
const result3 = addTwoNumbers(l5, l6);
console.log(linkedListToArray(result3)); // Output: [8, 9, 9, 9, 0, 0, 0, 1]

This code creates a ListNode class representing each node in the linked list. Then, it defines the addTwoNumbers function to add two linked lists representing non-negative integers. Finally, it provides some test cases to demonstrate the usage of the function.