Last Updated: 26 Sep, 2020
Add First and Second Half
Moderate
Asked in companies
You are given a Singly 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 the 1st half and 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 Linked List: 1-2-3-4-5-5-6
First half: 1-2-3-4
Second half: 5-5-6
Output Linked List: 1-7-9-0 = (1234 + 556 = 1790)
Follow Up:
Can you add both halves without finding the length of Linked List and in O(1) space?
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 :
Print a single line containing a string that denotes the required sum.
Note:
You are not required to print the output, it has already been taken care of. Just implement the function.
Constraints :
0 <= N <= 10^5
0 <= DATA <= 9
Where 'DATA' is the integer corresponding to the value of nodes of the given Linked List.
Time Limit: 1 sec
Approaches
In this approach, we will first iterate through the Linked List and find the length of the given Linked List. Then we will initialize two Linked List ‘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 both the lists so that their head nodes contain the least significant digits of both numbers.
Now the task remain is to add two numbers represented by two Linked List 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.
In this approach, instead of finding the length of the Linked List in one traversal, we will use two pointers ‘SLOW and ‘FAST’ to traverse the list. The ‘SLOW’ pointer will point to the next node and the ‘FAST’ pointer will skip one node and will points to the next of the next node after one iteration.
Now we will do changes in the given Linked List and store the two heads ‘HEAD1’ and ‘HEAD2’ for both halves. While traversing the given list reverse it until the fast pointer become null. In this way, we will have our first half with head ‘HEAD1’ and the least significant digit in the head itself. Similarly, we will store the second half in the reversed order while traversing to the rest half using the slow pointer.
Now we will add both the lists and store the results in one of the lists itself in the reversed order and return the head.