Add First and Second Reversed Half

Moderate
0/80
Average time to solve is 42m
34 upvotes
Asked in company
Nagarro Software

Problem statement

You have been given a Linked List of 'N' nodes such that each node represents a single digit.

Your task is to return a node 'X', where 'X' represents the head of the Linked List storing the digits of the sum(most significant digit at the head) formed by adding 1st half and reverse of 2nd half of the given linked list.

Note:

1. When 'N' is odd consider the middle element to be part of 1st half.
2. The sum should not contain any leading zero, except the number 0 itself.

For example:

Given a Linked List: 1-2-3-4-5-5-6

First half: 1-2-3-4   
Reversed second half: 6-5-5

Output linkedlist: 1-8-8-9 = (1234 + 655 = 1889)

Follow Up:

Can you add both halves without finding the length of LinkedList and in O(1) space?
Detailed explanation ( Input/output format, Notes, Images )
Input format : 
A single line of input contains the elements of the singly linked list separated by a single space and terminated by -1.
Output format : 
For each input, print a single line containing a string denoting the required sum.
Note: 
You do not need to print anything; it has already been taken care of. Just implement the given function.
Constraints : 
0 <= 'N' <= 10 ^ 5
0 <= 'DATA' <= 9

Where 'N' is the number of nodes in linked list and 'DATA' is the integer value in each node.

Time Limit: 1 sec
Sample Input 1:
1 2 4 5 6 -1
Sample Output 1:
189
Explanation for Sample Input 1:
The first half of the given linkedlist is: 1-2-4
The second half of the given linkedlist is: 6-5
Sum of both parts = 124 + 65 = 189
Sample Input 2:
3 9 0 1 1 0 -1
Sample Output 2:
401
Hint

Find the length of linkedlist and divide it into two parts.

Approaches (2)
Brute Force

In this approach, we will first iterate through the LinkedList and find the length of the given linked list. Then we will initialize two LinkedList ‘HEAD1’ and ‘HEAD2’ to store the two numbers.

 

We will iterate on the linked list till half-length and create a new list to store the first half with a head equal to ‘HEAD1’. Similarly, we will keep the second half in a new list with a head equals to ‘HEAD2’. Now reverse only the first list(the second list already contains the least significant digit at its head)  so that the head node contains the least significant digit of the first number.

 

Now the task remaining is to add two numbers represented by two linked lists where the head of each denotes the least significant digit of two numbers. So to add them we will iterate on both simultaneously and keep on adding the corresponding digits with a flag for ‘CARRY’ and store the sum in a new list. This list will have the required sum with its least significant digit in the head. Now reverse the resultant list and return its head.

Time Complexity

O(N), where ‘N’ is the total number of nodes in LinkedList.

 

In the worst case, we will be iterating on the list twice. So the running time complexity is 2 * N with a complexity of O(N).

Space Complexity

O(N), where ‘N’ is the total number of nodes in LinkedList.

 

In the worst case, extra space is required to maintain the 3 new linked lists(2 for both halves and 1 for the resultant sum list).

Code Solution
(100% EXP penalty)
Add First and Second Reversed Half
Full screen
Console