Add Two Numbers Represented by Linked Lists

Problem Statement

In this problem add two numbers represented by linked lists, You will be given two numbers represented by two separate Linked List, and write a function that returns the sum list.

A sum list is a list that represents the sum of two input numbers (Linked List).

Rules :

• In both, the numbers list the digits are stored in a reverse order.
• Each of the nodes of the Linked List must contain a single digit.
• The two numbers (Linked List) do not contain any leading zero, except the number 0 itself.

Input Format :

• Two numbers are represented by two Linked List heads.

Output Format :

• Return the sum of the two input numbers which is represented by Linked List in reverse order.

Example

Let’s understand this problem add two numbers represented by linked lists with help of examples.

Example : 1

Input :

Output :

Explanation :

Let us now understand the above example in detail.

• In the above example, we are taking two Linked List as input, and we are considering them as numbers.
• Since it is given that the Linked List contains digits of the number in reverse order. The list l1 which consists of {2, 4, 3} nodes will be represented as the number 342, and the list l2 which consists of {5, 6, 4} nodes will be represented as the number 465.
• So, we need to return a resultant Linked List in the reverse order that should represent the sum of the above two Linked Lists, i.e., $342 + 465 = 807$.
• So, in the above example we will return the Linked List form of the number 807 in reverse order, that is, {7, 0, 8}.

Example : 2

Input :

Output :

Explanation :

Let us now understand the above example in detail.

• In the above example, we are taking two Linked List as input, and we are considering them as numbers.
• Since it is given that the Linked List contains digits of the number in reverse order. The list l1 which consists of {5, 1} nodes will be represented as the number 15, and the list l2 which consists of {7, 9, 3} nodes will be represented as the number 397
• So, we need to return a resultant Linked List in the reverse order that should represent the sum of the above two Linked Lists, i.e., $15 + 397 = 412$.
• So, in the above example we will return the Linked List form of the number 412 in reverse order, that is, {2, 1, 4}.

Input :

Output :

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.

Approach : 1

Let us begin with the brute force approach of adding two numbers represented by linked lists. We are going to use some extra space, and it is slow but should be mentioned during the interview.

Intuition :

In the brute force approach add two numbers represented by linked lists. To add two numbers, the simplest thing we can do is to reverse the two linked lists (as they contain the digits in reverse order). Then convert the two numbers in linked lists into integers. Add these integers and convert the sum back to a linked list such that it contains digits in reverse order.

In this approach, we will need to implement the following functions :

1. To reverse both the Linked List.
2. Covert both the Linked List into integer.
3. Find the sum of both integers.
4. Reverse the resultant integer and then convert it into a Linked List.

Algorithm :

Here is the brute force algorithm for this particular problem add two numbers represented by linked lists :

1. Firstly, reverse both the given Linked List l1 and l2.
2. Then, convert the numbers represented by both the linked list into integers n1 and n2.
3. Then, add both the numbers as $sum = n1 + n2$.
4. Then, convert the above-calculated sum back to a Linked List using the toLinkedList() function which will one by one take the digits from the end of the number passed and create a linked list using them. And finally, return it. Note, in the toLinkedList() function the number's digit will be added in reverse order. ans = to_linkedlist(sum).
5. Return the resultant linked list ‘ans’ containing the sum.
6. Note : This approach will not work for huge input numbers represented by Linked List, which is out of the range of integer, and it will throw an overflow error.

Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

Code in JAVA :

Output :

Code in C++ :

Output :

Code in Python :

Output :

Time Complexity

In this approach of adding two numbers represented by linked lists, Firstly, we are reversing both the list l1 and l2, then we are converting them into integers. So overall the time complexity for this code will be $O(n+m)$.

T.C : $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

Space Complexity

The space complexity for the above implementation will depend upon the number of digits in our final result (after calculating the sum). This is very obvious because, as we are expected to store our final result in a Linked List, for every digit there will be a linked list node. So, for $N$ digits, the total space taken by the linked list will be $O(N)$, assuming, $N$ is the number of digits in our final result sum. Since, we know the final sum will mainly depend upon the maximum number of digits, from each of the numbers provided to us. Hence, we can conclude that our space complexity will depend on $O(max(n,m))$, where $m$ and $n$ are the number of digits in num1 and num2 respectively.

Approach : 2

The above approach of adding two numbers represented by the problem of the linked list is a brute force approach, and it will work only for input numbers that are small enough to belong in the range of integer data. What if the number of digits in the input number is huge let's say 30 ? For this type of input, the above approach will not work and we need to improve upon it.

Let us now see a much better and optimal approach of adding two numbers represented by the problem of the linked list, which will even work perfectly for the input number's digit out of range of integer datatype.

Intuition :

Here in this approach of adding two numbers represented by the problem of the linked list, we are not going to convert the Linked List into an integer and then calculate the sum, but we will do it in place with the help of the two-pointer method. We can simply iterate both the linked lists and keep on calculating the sum of values in nodes. Along with that, we will also maintain a carry in which we will store the first digit of the sum that comes out to be two-digit in any node. While taking the sums we will add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration.

We can simply iterate the 2 linked lists and take the sum of the values in nodes along with maintaining a carry. While taking sums add the previous carry to it and add a new node to the result containing the last digit in the sum and update the carry for the next iteration.

Algorithm :

• We are going to use the two-pointer method to solve this problem.
• Firstly, we will use 2 pointers to store the head of each linked list and initialize a carry variable as 0. Note, in the case of Java there is no concept of pointers, so in Java, we are going to use 2 iterators.
• Then, we declare a pointer (iterator in case of Java) to the node to store our resultant answer represented by Linked List.
• We will iterate through both the linked list and keep on adding the digits pointed by the pointers. The moment we have reached the end of any one of the linked lists and we have no further nodes of that linked list, we will consider its value as 0 while iterating for the other linked list which is still having the nodes, and keep calculating the sum.
• We will add a new node with $(sum + carry)\%10$ as value to our answer and update carry as $(sum + carry) / 10$.
• We will keep on repeating steps 3 and 4 until we reach the end of both of the linked lists. If one of the Linked List is smaller in size than the other one, it gets ended before the other Linked List. In that case, we will continue the iteration, just in the place of the smaller Linked List’s value, we will add 0 until the other Linked List also gets over.
• After traversing both the linked lists, if the carry is greater than 0 $(carry > 0)$ then add this carry to our answer as a new node.

Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

Code in JAVA :

Output :

Code in C++ :

Output :

Code in python :

Output :

Time Complexity

In this approach add two numbers represented by the problem of the linked list, as we are traversing both the list l1 and l2, and we are calculating the sum of the numbers. So the overall time complexity for this code will be $O(n+m)$.

T.C : $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

Space Complexity

The overall space complexity of this approach will depend on the number of digits in the sum, which will depend on the number having more digits.

$O(max(n,m))$, as the number of digits in the sum will depend on the number having more digits.

Approach : 3

Now let us see another approach of how we can solve this add two numbers represented by linked lists problem with the help of a data structure stack, and how we can add the numbers of both the Linked List using a stack. This approach is not that efficient, as here we have to make sure that the size of the list should not exceed the limit of the stack, or it will throw an error of overflow.

Intuition :

In this approach we are going to use three stacks, out of which in two stacks s1, s2 we are going to store the nodes of both the Linked List and in the third stack s3 we will store the sum of the numbers of both the list inside the stacks s1, s2.

Algorithm :

• Firstly, we are going to create 3 stacks named s1, s2, and s3.
• Then, we will fill the stack s1 with Nodes of Linked List l1 and the stack s2 with Nodes of Linked List l2.
• We will initialize a carry variable in which we will store the first digit of the sum that comes out to be two-digit in any node. If the sum is greater than 9 we will set the carry as 1 else we will set the carry as 0.
• Now, we will start filling the stack s3 by creating new nodes and storing the data of that new node to the sum of s1.top(), and s2.top() and carry until both the list l1 and l2 are empty. We will create a Node (say prev) that will contain the head of the sum List inside the stack s3.
• Now, connect all the elements of s3 from top to bottom and then reverse the list as return prev.

Code

Now, let us see the code of adding two numbers represented by linked lists problem in different programming languages.

Code in JAVA :

Output :

Code in C++

Output :

Code in python :

Output :

Time Complexity

In this approach of adding two numbers represented by the problem of the linked list, as we are traversing both the list l1 and l2, we are storing them in stacks. So the overall time complexity for this code will be $O(n+m)$.

Time Complexity : $O(n+m)$, where $n, m$ are the number of nodes in the linked lists.

Space Complexity

In the above implementation, we are storing the nodes of both the Linked List inside two different stacks, so it will occupy $O(n) + O(m)$ space, where n and m are the size of both the Linked list. Now, we are storing their sum inside another stack which will again occupy a space of $O(max(n, m))$ as discussed above, the space of the sum will depend upon the input number of more digits. So the overall space will be $O(n + m + max(n,m))$.

$O(n) + O(m) + O(max(n,m))$. However, this approach is not much efficient as we are using a lot of space here.

Learn More

Find the Middle Element in Linked List