Add Linked Lists

Posted: 3 Dec, 2020
Difficulty: Easy

PROBLEM STATEMENT

Try Problem

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.

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
Approach 1

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.
Try Problem