Add Numbers Represented by Linked Lists in Java

It is a very interesting problem frequently asked in interviews of top IT companies like Google, Amazon, TCS, Accenture, etc. By solving the problem, one wants to check the logical ability, critical thinking, and problem-solving skill of the interviewee. So, in this section, we are going to solve how to add numbers represented by linked list in Java with different approaches and logic. Also, we will create Java programs for the same.

Problem Statement

Two linked lists are given. Each linked list represents a number. The task is to find the sum of the numbers represented by each linked list. The answer has to be in the form of a linked list. Observe the following examples.

Example 1:

Input:

L1 = 7 -> 9 -> 0 -> 5 -> 9 -> 1 -> 2 -> NULL

L2 = 5 -> 3 -> 8 -> 4 -> 3 -> 6 -> 4 -> NULL

Output: 1 -> 3 -> 2 -> 9 -> 0 -> 2 -> 7 -> 6 -> NULL

Explanation: The number represented by the list L1 is 7905912 and the number represented by the list L2 is 5384364, and their sum is 7905912 + 5384364 = 13290276.

Example 2:

Input:

L1 = 9 -> 8 -> 0 -> 4 -> 3 -> 6 -> 2 -> NULL

L2 = 8 -> 5 -> 7 -> NULL

Output: 9 -> 8 -> 0 -> 5 -> 2 -> 1 -> 9 -> NULL

Explanation: The number represented by the list L1 is 9804362 and the number represented by the list L2 is 857, and their sum is 9804362 + 857 = 9805219.

Solution to the Problem

Approach: Using Recursion

We know that the sum of two numbers can be found by adding digits from right to left. Therefore, it is required to reverse the given linked lists. Though, we will not be literally reversing the linked list. We will imitate the same using recursion. We will do the basic sum that we have learned in our primary classes. After finding the sum, construct a new linked list that shows the sum. Illustration of the same is mentioned below.

FileName: NumberSumLinkedList.java

Output:

First List is 7 9 0 5 9 1 2  
Second List is 5 3 8 4 3 6 4  
Resultant List is 1 3 2 9 0 2 7 6  


First List is 9 8 0 4 3 6 2  
Second List is 8 5 7  
Resultant List is 9 8 0 5 2 1 9  

Complexity Analysis: Since for the addition, we have to traverse both lists. Therefore, the time complexity of the program is O(a + b), where a is the total number of elements present in the first linked list, and b is the total number of elements present in the second linked list. The space complexity of the program is also O(a + b), as we also need to store the resultant linked list.

Approach: Using Iteration

In this approach, we will be using a stack to store the elements of both linked lists. We know that a stack works in a Last In First Out (LIFO) manner. Therefore, the last node will be popped out first. On the popped elements from both the linked list, we do the add operation.

FileName: MajorityEle1.java

Output:

First List is 7 9 0 5 9 1 2  
Second List is 5 3 8 4 3 6 4  
Resultant List is 1 3 2 9 0 2 7 6  


First List is 9 8 0 4 3 6 2  
Second List is 8 5 7  
Resultant List is 9 8 0 5 2 1 9  

Complexity Analysis: The time, as well as the space complexity of the program is the same as the above.