Posted: 16 Feb, 2021
Difficulty: Moderate

## PROBLEM STATEMENT

#### You are given two linked lists representing two non-negative numbers. The digits in the linked list are stored in reverse order, i.e. starting from least significant digit (LSD) to the most significant digit (MSD), and each of their nodes contains a single digit. Your task is to find the sum list and return the head of the sum list where the sum list is a linked list representation of the addition of two numbers.

##### Note :
``````The number represented by the linked lists do not contain any leading zeros.
``````
##### Input Format:
``````The first line of input contains a single integer T, representing the number of test cases.

Then the T test cases follow.

The first line of each test case contains the elements of the first singly linked list separated by a single space and terminated by -1.

The second line of each test case contains the elements of the second singly linked list separated by a single space and terminated by -1.
``````
##### Output Format:
``````For each test case, print the sum linked list. The elements of the sum list should be single-space separated and terminated by -1.

The output of each test case must be printed on a separate line.
``````
##### Note :
``````You do not need to print anything; it has already been taken care of. Just implement the given function.
``````
##### Constraints :
``````1 <= T <= 10
1 <= M, N <= 5 * 10^4
0 <= data[i] <= 9 and data[i] != -1

Where 'M' and 'N' are the number of nodes in the two linked lists, 'data[i]' is the data of the 'i-th' node.

Time Limit: 1 sec
`````` Approach 1
• A simple approach could be to recursively add the nodes of the linked list while keeping track of the carry generated.
• The idea behind this approach is the same as finding the sum of two numbers manually on a paper, where we start by adding the LSD and move on till the MSD. Also, keeping track of the carry generated in every iteration.
• As the linked lists represent the numbers in reverse order, the LSD occurs at the starting of the list and MSD occurs at the ending.
• So to perform the addition, we can add the corresponding nodes (i.e. nodes present at the same position) of the two linked lists to generate the resulting digit in the sum list.
• While adding, it is possible that the sum of the two nodes is greater than 9. This will generate a carry that needs to be added to the next significant digit.
• In case one of the lists has more number elements than the other, then we consider the remaining values of the other list as 0.

The steps are as follows:

• Let the recursive function be addTwoNumbersHelper('NODE1', 'NODE2', 'CARRY') which takes the current node of the first list, the current node of the second list, and the carry generated from the previous iteration/addition.