Register for our webinar

1 hour

Step 1

Step 2

Congratulations!

You have registered for our webinar

Oops! Something went wrong while submitting the form.

Step 1

Step 2

Confirmed

You are scheduled with Interview Kickstart.

Redirecting...

Oops! Something went wrong while submitting the form.

Write a function which adds two numbers `a`

and `b`

, represented as linked lists of size `lenA`

and `lenB`

respectively, and returns the sum of `a`

and `b`

in the 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).

```
{
"l_a": [7, 5, 2],
"l_b": [2, 0, 3]
}
```

Output:

```
[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.

```
{
"l_a": [5, 8, 3],
"l_b": [9, 4, 1]
}
```

Output:

```
[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.

- There are two input parameters
`l_a`

and`l_b`

, denoting linked lists representing numbers`a`

and`b`

respectively. - Output is the head node of resultant linked list representing the sum of two numbers
`a`

and`b`

.

Constraints

- 1 <= length of the input linked lists <= 100000
- 0 <= linked list node value <= 9
- Leading zeros will not appear in the input and will not be accepted in the output.
- No negative numbers.

We have provided three solutions. We will refer to the length of `l_a`

and `l_b`

as `lenA`

and `lenB`

, respectively.

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
`i`

-th significant digit of`x`

and`y`

and add`carryForward`

to it(Let us say this sum`sumD`

). If at`i`

-th 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`i`

-th significant digit of result to`sumD % 10`

. `i = i + 1`

, Repeat #3 till`i <= N - 1`

.- If
`carryForward > 0`

, set`N`

-th 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, `i`

-th node in linked list will be `i`

-th 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)).

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)).

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

.

O(lenA + lenB).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(max(lenA, lenB))

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(max(lenA, lenB)) + O(max(lenA, lenB)) = O(lenA + lenB).

```
/*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(max(lenA, lenB)).
* Auxiliary space: O(max(lenA, lenB)).
* Total space: O(lenA + lenB).
*/
static LinkedListNode add_two_numbers(LinkedListNode l_a, LinkedListNode l_b) {
// To store carry while adding two numbers
int carryForward = 0;
// Creating another singly linked list to store resultant sum
LinkedListNode result = new LinkedListNode(-1);
// To store head of result list, so we can return at the end of function
LinkedListNode head = result;
while(l_a != null || l_b != null) {
int l_a_data = 0;
if(l_a != null) {
l_a_data = l_a.value;
l_a = l_a.next;
}
int l_b_data = 0;
if(l_b != null) {
l_b_data = l_b.value;
l_b = l_b.next;
}
int sum = l_a_data + l_b_data + carryForward;
// If it's first node of result linkedlist then update data from -1 to sum % 10.
if(result.value == -1) {
result.value = sum % 10;
}
else{
// Create new next node in result linkedlist.
LinkedListNode new_node = new LinkedListNode(sum % 10);
result.next = new_node;
result = result.next;
}
carryForward = sum / 10;
}
// If still carry is remaining then create another node in result linkedlist to store carry.
if(carryForward > 0){
LinkedListNode new_node = new LinkedListNode(carryForward);
result.next = new_node;
}
// Result head node
return head;
}
```

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).

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).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

```
/*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(lenA + lenB).
* Auxiliary space: O(1).
* Total space: O(lenA + lenB).
*/
static LinkedListNode add_two_numbers(LinkedListNode l_a, LinkedListNode l_b) {
int lenA = 0, lenB = 0;
// Finding length of l_a
LinkedListNode travA = l_a;
while (travA != null) {
lenA++;
travA = travA.next;
}
// Finding length of l_a
LinkedListNode travB = l_b;
while (travB != null) {
lenB++;
travB = travB.next;
}
// if lenA > lenB, swap linked list pointers, so that after this point onwards,
// l_a contains smaller length linked list out of given two input linked lists
if (lenA > lenB) {
LinkedListNode l_temp = l_a;
l_a = l_b;
l_b = l_temp;
}
int carryForward = 0;
travA = l_a;
travB = l_b;
while (true) {
// ith iteration of this loop denotes that we are processing ith significant digit
int l_a_data = (travA == null) ? 0 : travA.value;
// let say sumD = travB.value + travA.value + carryForward
travB.value += l_a_data + carryForward;
// Setting carryForward = sumD/10
carryForward = travB.value / 10;
// In ith iteration, setting ith significant digit of sum = sumD % 10
travB.value = travB.value % 10;
// Moving on to (i + 1)th significant digit
if(travA != null)
travA = travA.next;
if (travB.next == null){
// If carryForward > 0, Adding a node in l_b, which denotes new most significant digit of sum
// as there is no more digit to carry forward the carryForward
if (carryForward > 0) {
LinkedListNode new_node = new LinkedListNode(carryForward);
travB.next = new_node;
}
break;
}
travB = travB.next;
}
return l_b;
}
```

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)).

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).

Space used for input: O(lenA + lenB)

Auxiliary space used: O(1)

Space used for output: O(max(lenA, lenB))

So, total space complexity: O(lenA + lenB) + O(1) + O(max(lenA, lenB)) = O(lenA + lenB).

```
/*
* Asymptotic complexity in terms of lengths of the first and second number, \`lenA\` and \`lenB\`:
* Time: O(max(lenA, lenB)).
* Auxiliary space: O(1).
* Total space: O(lenA + lenB).
*/
static LinkedListNode add_two_numbers(LinkedListNode l_a, LinkedListNode l_b) {
LinkedListNode result = l_b;
// We are storing resultant sum in l_b.
int carryForward = 0, sum = 0;
// To store carry and current sum.
// We are iterating till we reach at end of one of linkedlist.
// and update l_b with resultant sum.
while(true){
sum = l_a.value + l_b.value + carryForward;
l_b.value = sum % 10;
carryForward = sum / 10;
if(l_a.next == null || l_b.next == null){
break;
}
l_a = l_a.next;
l_b = l_b.next;
}
// If we reached the end of l_b but not of l_a, we can utilize the already created nodes
// of l_a by appending them to l_b.
if(l_a.next != null && l_b.next == null){
l_b.next = l_a.next;
}
// We iterate through remaining nodes of l_b and update it with sum of node and carry.
while(carryForward > 0 && l_b.next != null){
l_b = l_b.next;
sum = carryForward + l_b.value;
l_b.value = sum % 10;
carryForward = sum / 10;
}
// If still carry is remaining then we add extra node at tail of linkedlist l_b.
if(carryForward > 0){
LinkedListNode new_node = new LinkedListNode(carryForward);
l_b.next = new_node;
}
// Result will be head node of l_b (which is storing our resultant sum)
return result;
}
```

We hope that these solutions to add two numbers problem have helped you level up your coding skills. You can expect problems like these at top tech companies like Amazon and Google.

If you are preparing for a tech interview at FAANG or any other Tier-1 tech company, register for Interview Kickstart's FREE webinar to understand the best way to prepare.

Interview Kickstart offers interview preparation courses taught by FAANG+ tech leads and seasoned hiring managers. Our programs include a comprehensive curriculum, unmatched teaching methods, and career coaching to help you nail your next tech interview.

We offer 18 interview preparation courses, each tailored to a specific engineering domain or role, including the most in-demand and highest-paying domains and roles, such as:

- Back-end Engineering Interview Course
- Front-end Engineering Interview Course
- Full Stack Developer Interview Course

To learn more, register for the FREE webinar.

Note: Input and Output will already be taken care of.