Learn how to create an algorithm to add two numbers represented by linked lists in javascript.
Example
Input: 2 -> 4 -> 3 -> 7 -> 9 -> null 5 -> 6 -> 8 -> null Output: 7 -> 0 -> 2 -> 8 -> 9 -> null
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.
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 to 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
Time complexity: O(max(m, n)).
Space complexity: O(max(m, n)).
