Add Linked Lists

Easy
0/40
Average time to solve is 20m
profile
Contributed by
9 upvotes
Asked in companies
Morgan StanleyQualcommIntuit

Problem statement

Given two numbers represented by linked lists. Your task is find the sum list and return the head of the sum list.

The sum list is a linked list representation of addition of two numbers.

Detailed explanation ( Input/output format, Notes, Images )
Input Format : 
The first line of input contains a single integer T, representing the number of test cases or queries to be run. 

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. Hence, -1 would never be a list element.

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. Hence, -1 would never be a list element.
Output Format : 
For each test case, print the sum linked list. The elements of the sum list should be single-space separated, terminated by -1.

The output of each test case is printed in a separate line.
Note : 
You do not need to print anything, just return the head of the sum linked list.
Constraints : 
1 <= T <= 10
1 <= N <= 5 * 10^4
0 <= data <= 9 and data != -1


Time Limit : 1sec
Sample Input 1 :
1
5 6 3 -1
8 4 2 -1
Sample Output 1 :
1 4 0 5 -1
Explanation of Sample Input 1 :
563 + 842 = 1405
Sample Input 2 :
2
7 5 9 4 6 -1
8 4 -1
0 2 3 4 0 -1
0 0 1 -1
Sample Output 2 :
7 6 0 3 0 -1
2 3 4 1 -1
Explanation of Sample Input 2 :
75946 + 84 = 76030
02340 + 001 = 2341
Hint

Can you solve it using recursion?

Approaches (2)
Recursive approach

One way is to recursively add the two linked lists. Keep the nodes in the recursion stack and add the last nodes first and then second last and so on. Initially, find the size of both the linked lists. If both the linked lists are of the same size, add them using recursion. Else if their sizes differ, move the head pointer of the larger linked list forward K times, where K is the difference between the number of nodes in the larger linked list and the smaller one. Now calculate the sum of these two linked lists using recursion and add the carry of the resultant list and the left part of the larger linked list.

Algorithm : 

  1. Calculate sizes of given two linked lists.
  2. If both the lists are of same size, then calculate their sum using recursion. Hold all nodes in the recursion call stack, till the rightmost node. Calculate sum of the rightmost nodes and forward carry to the left side. If at the end of addition, a non zero carry exists, insert it at the beginning of the sum list through a new Linked List node.
  3. If the lists differ in size. Let the difference be ‘diff’. 
    a.  Move diff nodes ahead in the larger linked list. Now use step 2 to add the smaller list and the right sub-list of the larger list. Also store the carry of this sum.
    b.  Add the carry and the left part of the larger linked list.
    c.  Append the nodes of this sum list are at the beginning of the previous sum list calculated in 3a.
  4. Return the head of the sum list.
Time Complexity

O(N+M), where ‘N’ and ‘M’ are the number of nodes in the first and the second linked list respectively.

 

Every node of the both the linked lists is visited twice to calculate the size of the lists and to perform the addition operation. So the time complexity is O(2*(N+M)) = O(N+M).

Space Complexity

O(max(N,M)), where ‘N’ and ‘M’ are the number of nodes in the first and the second linked list respectively. 

 

After moving the pointer on the larger list to the node from where its size is equal to the size of the smaller linked list, both the lists to be added are now of min(N,M) size. Both the lists use recursion stack to store the nodes until the rightmost node is reached. This results into a space complexity of O(2*(min(N,M))). Also, a new linked list is created for storing the sum of the two linked lists, which results in a space complexity of O(max(N,M)). 

Final space complexity will be  O(min(N,M)) + O(max(N,M)) = O(max(N,M)).

Code Solution
(100% EXP penalty)
Add Linked Lists
Full screen
Console