Add two numbers represented by linked lists

Learn how to create an algorithm to add two numbers represented by linked lists in Javascript.

The numbers in the linked list are represented in reverse order for example 2 -> 4 -> 3 -> 7 -> 9 -> null = 97342 and 5 -> 6 -> 8 -> null = 865 which is equal to 97342 + 865 = 98207 = 7 -> 0 -> 2 -> 8 -> 9 -> null.

Example

Input:
2 -> 4 -> 3 -> 7 -> 9 -> null
5 -> 6 -> 8 -> null

Output:
7 -> 0 -> 2 -> 8 -> 9 -> null

One simple way to solve this is reverse the list or add the elements in the stack and form the number from it and add those numbers then add each digits from those in a new linked list and return it.

Here we will use two different examples which will add the numbers without reversing the linked list.

One will use extra space while other will work inplace.

Add two numbers represented by linked lists using extra space

We just need to add each number in the list just like we do the addition and keep track of carry. In the next addition add that carry along with the sum and so on.

In the end if there is still value in the carry then add it at the end.

const llSum = (l1, l2) => {
    if (!l1) return l2;
    if (!l2) return l1;

    let carry = 0;
    let result = null,
        head = null;

    //Iterate both the list
    while (l1 || l2) {
        let sum = 0;

        if (l1) {
            sum += l1.element;
            l1 = l1.next;
        }

        if (l2) {
            sum += l2.element;
            l2 = l2.next;
        }

        //Calculate the sum
        sum += carry;

        //Get the new number from the sum
        const value = Math.floor(sum % 10);

        //Get the carry
        carry = Math.floor(sum / 10);

        //Create the new node
        let node = new Node(value);

        //Add the new node with number to the list
        if (result) {
            result.next = node;
            result = result.next;
        } else {
            result = head = node;
        }
    }

    //If there is carry
    //Then add it at the end
    if (carry) {
        result.next = new Node(carry);
    }

    //Return the head
    return head;
};

Input:
const ll1 = new linkedlist();
const ll2 = new linkedlist();

ll1.append(2);
ll1.append(4);
ll1.append(3);
ll1.append(7);
ll1.append(9);

ll2.append(5);
ll2.append(6);
ll2.append(8);

let s = llSum(ll1.getHead(), ll2.getHead());

while (s) {
    console.log(s.element);
    s = s.next;
}

Output:
7
0
2
8
9

Time complexity: O(max(m, n)).

Space complexity: O(max(m, n)).

Adding the list in place.

To do the addition in place.

We iterate the list till both the list have values.
And store the sum of two numbers in any of the list.
We use two reference to track the list in which we are storing the sums.
At the end if there is still numbers left in any of the list then copy those numbers in the list which we are storing the sums and keep on adding the carry values to them.
In the end if there is still value in carry at that at the end and return the list.

const llSumInplace = (l1, l2) => {
    if (!l1) return l2;
    if (!l2) return l1;

    let carry = 0;
    //Track the list
    let prev = null,
    head = l1;

    //Iterate both the list
    while (l1 && l2) {
        let sum = 0;

        //Calculate the sum
        sum += carry + l1.element + l2.element;

        //Get the new number from the sum
        const value = Math.floor(sum % 10);

        //Get the carry
        carry = Math.floor(sum / 10);

        //Update the new value in the first list.
        l1.element = value;
        prev = l1;

        l2 = l2.next;
        l1 = l1.next;
    }

    //If there is still item in any of the list then keep the addition
    if (l1 || l2) {
        //If the second list has more values then copy them in first list and continue addition
        if (l2) prev.next = l2;
        l1 = prev.next;

        //Keep adding the carry for the remaining numbers in the first list
        //And update the values.
        while (l1) {
            let sum = carry + l1.element;

            const value = Math.floor(sum % 10);

            carry = Math.floor(sum / 10);

            //Update the new value
            l1.element = value;
            prev = l1;

            l1 = l1.next;
        }
    }

    //If there is carry
    //Then add it at the end
    if (carry) {
       prev.next = new Node(carry);
    }

    //Return the head
    return head;
};

Input:
const ll1 = new linkedlist();
const ll2 = new linkedlist();

ll1.append(2);
ll1.append(4);
ll1.append(3);
ll1.append(7);
ll1.append(9);

ll2.append(5);
ll2.append(6);
ll2.append(8);

let s = llSumInplace(ll1.getHead(), ll2.getHead());

while (s) {
    console.log(s.element);
    s = s.next;
}

Output:
7
0
2
8
9