Last Updated: 3 Dec, 2020

Add Linked Lists

Easy

Asked in companies

Solve now

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.

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

Solve now

Approaches

01 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 :

Calculate sizes of given two linked lists.
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.
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.
Return the head of the sum list.

Solve now

02 Approach

The idea is to use the simple method of adding two numbers. We add two numbers starting from their least significant digit and moving towards the most significant digit. So we need to access the nodes of linked lists from last to first. First step would be to reverse both the linked lists. Then add both the linked lists starting from their heads and then reverse the resulting sum list and return its head.

Algorithm :

Reverse both the linked lists.
Add corresponding nodes of the two linked lists and take the carry forward, if any. If the value of carry after addition is non-zero, insert the carry at the end of the sum list through a new linked list node.
Reverse the added linked list and return its head.

Solve now