Write a function which adds two numbers a and b, represented as linked lists of size lenA and lenB respectively, and returns the sum c in form of a new linked list.

Ignoring the allocation of a new linked list, try to use constant memory when solving it.

A number is represented by a linked list, with the head of the linked list being the least significant digit. For example 125 is represented as 5->2->1, and 371 is represented as 1->7->3. Adding 5->2->1(125) and 1->7->3(371) should produce 6->9->4(496).

Input:

l_a = 7->5->2

l_b = 2->0->3

Output: result = 9->5->5

As l_a = 7->5->2 means number 257 and l_b = 2->0->3 means number 302. Sum of 257 and 302 is 559 so, result will represent 9->5->5.

Input:

l_a = 5->8->3

l_b = 9->4->1

Output: result = 4->3->5

As l_a = 5->8->3 means number 385 and l_b = 9->4->1 means number 149. Sum of 385 and 149 is 534 so, result will represent 4->3->5.

Input Parameters: There will be two arguments l_a and l_b, denoting linked lists representing numbers a and b respectively

Output: Return result denoting head node of resultant sum linked list.

• 1

• 0

• Leading zeros will not appear in the input and will not be accepted in the output.

• No negative numbers.

**Solutions**

Let's have a look at an approach for having sum of two numbers x and y represented in decimal number system:

(Let us say string representation of number is num_str, then Least significant digit means digit represented by character at 0th index of num_str and Most significant digit means digit represented by character at (len(num_str) - 1)th index of num_str).

• Add trailing zeroes to make the lengths of x and y equal(in decimal system). Let us say this length is N.

• Set carryForward=0 and i=0.

• Add ith significant digit of x and y and add carryForward to i t(Let us say this sum 'sumD'). If at ith significant digit, sumD is greater than 9, we carry forward the tenth place digit of sumD to the next significant digit.

• Set carryForward = sumD/10 and ith significant digit of result to sumD % 10.

• i=i+1, Repeat #3 till i

• If carryForward>0, set nth significant digit of result as carryForward.

• Return result.

Now, as numbers are represented as a linked list, with the head of the linked list being the least significant digit, ith node in linked list will be ith least significant digit of the number. We need to start traversing linked lists corresponding to given two numbers starting from their heads and follow the above mentioned steps.

In this solution, we are creating an extra linked list to store resultant sum. In an actual interview, ignore the allocation of a new linked list, try to use constant memory when solving it. But if the interviewer asks for the solution which does not modify the input linked lists, then this is the expected solution.

O(Max(lenA, lenB)) where lenA and lenB are the linked list lengths.

As we are iterating over the given linked list l_a and l_b simultaneously in one iteration. Hence complexity is maximum of length of l_a and length l_b.

O(Max(lenA, lenB)) where lenA and lenB are the linked list lengths.

We are storing the resultant sum by creating a new linkedlist and the size of that newly created linked list can be 1 + Max(lenA, lenB).

O(lenA+lenB) where lenA and lenB are the linked list lengths.

Input will have two linked lists l_a and l_b of lenA and lenB respectively, so input takes O(lenA+lenB) and auxiliary space used is O(Max(lenA, lenB)).

So, O(lenA+lenB) + O(Max(lenA, lenB)) → O(lenA+lenB)

Approach will be as similar as explained other_solution1, but this approach is bit optimised in terms of space used as we will not create a new linked list to store the resultant sum rather than use one of the linked list l_a or l_b. We are iterating over given two linked lists to find out which one is longer and always making sure that l_b will always be the longer linked list to store the resultant sum if not then by swapping l_a and l_b.

O(lenA+lenB) where lenA and lenB are the linked list lengths.

As we are iterating over two given linked lists l_a and l_b. Hence complexity is the sum of their lengths.

O(1).

We aren’t storing anything extra and using one of the two given linked list to store the resultant sum.

O(lenA+lenB) where lenA and lenB are the linked list lengths.

Input will have two linked lists l_a and l_b of lenA and lenB respectively, so input takes O(lenA+lenB) and auxiliary space used is O(1).

So, O(lenA+lenB) + O(1) → O(lenA+lenB)

Approach will be as similar as explained other_solution1, but this approach is optimised in terms of number of iterations and extra space used as we are storing the resultant value in one of the given two input linked list only so, we don’t require to create and allocate new linked list.

And we are not finding the longer linked list by iterating over given two linked list as we were doing in other_solution2 but when finding the resultant sum we are changing the pointer and appending the longer list’s remaining nodes to the linked list in which we are storing the resultant sum.

For more detailed explanation refer optimal_solution.

O(Max(lenA, lenB)) where lenA and lenB are the linked list lengths.

As we are iterating over the given linked list l_a and l_b simultaneously in one iteration. Hence complexity is maximum of length of l_a and length l_b.

O(1).

We aren’t storing anything extra and using one of the two given linked lists to store the resultant sum.

O(lenA+lenB) where lenA and lenB are the linked list lengths. Input will have two linked lists l_a and l_b of lenA and lenB respectively, so input takes O(lenA+lenB) and auxiliary space used is O(1).

So, O(lenA+lenB) + O(1) → O(lenA+lenB)