Add two number as linked lists — Asked in Google Microsoft and Adobe Interviews

Problem Statement :

You have been given two singly Linked Lists, where each of them represents a positive number without any leading zeros.

Your task is to add these two numbers and print the summation in the form of a linked list.

Given :

1 1 -1
9 9 9 -1

Output :

1 0 1 0 -1

Explanation of given Test Cases :

We are adding 11 and 999 to get 1010.

Approach :

Naive Method

We will use the naive method to add two linked lists. While adding two numbers, we always add digits in the right to left manner. So first, we will reverse both linked lists so that we can easily process the number in this manner.

We will be storing the result of the addition in a different linked list. We will start adding the nodes of both linked lists and use another variable ‘carry’ to keep track of the carry generated in each addition.

In the end, if we are left with a ‘carry’ greater than 0, we will just add a new node in our answer linked list.

Constant Space

We will use the same naïve method to add two linked lists. Like the previous approach, we will reverse both linked lists so that we can easily process the number in this manner.

Now, we will start adding the nodes of both linked lists and use another variable ‘carry’ to keep track of the carry generated in each addition. We will be updating either of the linked lists to their sum. Hence, we will not be using any extra space for storing the result.

In the end, if we are left with a ‘carry’ greater than 0, we will just add a new node in our resultant linked list.

Time Complexity: O(N + M)
Space Complexity: O(1)

Code :

Thanks for Reading

Placewit grows the best engineers by providing an interactive classroom experience and by helping them develop their skills and get placed in amazing companies.

Learn more at Placewit. Follow us on Instagram and Facebook for daily learning.