# Add Two Linked Lists #### Try First, Check Solution later

1. You should first read the question and watch the question video.
2. Think of a solution approach, then try and submit the question on editor tab.
3. We strongly advise you to watch the solution video for prescribed approach.

`1. You are given a partially written LinkedList class.2. You are required to complete the body of addLinkedLists function. The function is passed two linked lists which represent two numbers - the first element is the most significant digit and the last element is the least significant digit. The function is expected to add the two linked list and return a new linked list.The following approaches are not allowed :    1. Don't reverse the linked lists in order to access them from least significant digit      to most significant.     2. Don't use arrays or explicit extra memory.     3. Don't convert linked lists to number, add them up and convert the result back      to a linked list.Hint - You are expected to take help of recursion to access digits from least significant to most significant. You have to tackle the challenge of unequal size of lists and manage carry where required.3. Input and Output is managed for you. Note-> Make sure to set head and tail appropriately because addFirst and addLast has been used to test their values in the input-output code.`
Input Format
`Input is managed for you`
Output Format
`Output is managed for you`
Question Video
Constraints
`1. Time complexity -> O(n)2. Space complexity -> Recursion space, O(n)`
Sample Input
`1139 9 91020`
Sample Output
`1 9 9 9 1 0 0 0 10 1 0 0 0 20 `

• Editorial

The problem here deals with adding two linked list wherein we are not allowed the following operations:

1. We are not allowed convert the list to integers

2. We are not allowed to convert the list to arrays

3. We are not allowed to reverse the list

To solve this problem we will use a recursive approach. The idea here is that we need to add the list but as we know that addition is only possible when traversing from the end like adding firstly the unit place elements and then carry forwarding to the next place and so on. This generalized process here we will try to implement using recursion as we are not allowed to reverse the list.

Here we will be passing the current element and its place as parameters to the recursive function and we will make recursive calls till we hit the base case. Our recursive function is built to return the carry forward number if any. So for the base case when we have no elements after the unit place (which is true) then we return 0. Now for the unit place, we have supposed both the numbers so we add the unit places with the carry number and then add the resultant number at the head of the global resultant linked list. Adding it to the head always ensure that firstly unit place is placed at head later on the tenth place is added and then hundredth place and so on this makes our resultant list to be in order and hence no need to reverse the obtained result.

To summarize we are traversing over the lists until we hit the base case, thereafter when we are popping out from the recursive stack we are entering the result at its correct place and returning the carry value. Also, we are keeping a track of lists with different digits to avoid miscalculation, as in that case when one element is not long enough to avoid error we are not considering it (this explains the if conditions in the code).  Below is the implementation in Java:

```public static LinkedList addTwoLists(LinkedList one, LinkedList two) {
if(carry > 0){
}
return res;
}
public static int addTwoLists(Node on, Node tn, int pio, int pit, LinkedList res){
if(on == null && tn == null){
return 0;
}
int carry = 0;
int data = 0;
if(pio > pit){
carry = addTwoLists(on.next, tn, pio - 1, pit, res);
data = carry + on.data;
} else if(pio < pit){
carry = addTwoLists(on, tn.next, pio, pit - 1, res);
data = carry + tn.data;
} else {
carry = addTwoLists(on.next, tn.next, pio - 1, pit - 1, res);
data = carry + on.data + tn.data;
}
carry = data / 10;
data = data % 10;
return carry;
}```

java false

Time Complexity: O(max(n,m))

The time complexity for the function is linear as we are recursively calling the function for the length of the longer list.

Space Complexity: O(max(n,m))

The space complexity for the function is linear we are recursively calling the function for the length of the longer list along with the additional space used for storing the resultant list.

• Related Topics

Run

Run
Id Name