Last Updated: 1 Apr, 2021
Replace The Linked List
Moderate
Asked in companies
Given a linked list containing a series of numbers that are separated by ‘0’. You need to find the sum of the series and replace the series’s elements with its sum.
For Example :
If the given linked list is 3 ->4 ->0 ->5 ->0, you should return linked list as - 7 -> 5.
Note :
You need to replace the sum values in the linked list without using any extra space.
It is guaranteed that there will be no two consecutive zeroes in the linked list.
Input Format :
The first line of input contains an integer ‘T’ denoting the number of test cases.
The first line of each test case contains integers denoting the nodes of the linked list. Each line is guaranteed to have -1 at the end to signify the end of the linked list. Also, None of the elements of the linked list is -1.
Output Format :
For each test case, print space-separated integers denoting the nodes of the output linked list, in a separate line.
Each new line denotes a separated linked list.
Note :
You don't need to print anything, it has already been taken care of. Just implement the given function.
Constraints :
1 <= T <= 50
1 <= N <= 10^5
-10^9 <= data <= 10^9
data ≠ -1.
Time Limit: 1 sec
Approaches
The simple idea is to traverse the linked list and store the sum of nodes in a variable ‘sum’ until ‘0’ is not encountered. We will store this ‘sum’ value in every series’s first node and link all these nodes containing sum values.
Algorithm:
- Create a pointer “res” initially pointing to the head of the linked list that will point to every series’s first node and store the sum value of that series.
- Take a pointer “current” that will help in traversing the linked list.
- Iterate through the linked list until “current” does not point to NULL.
- If ‘current’ node data is not ‘0’, add nodes’ values in a variable ‘ sum ‘ and move the current pointer to the next node.
- If the current node’s data is ‘0’, we will store the ‘sum’ value at the ‘res’ node.
- We have to remove all the nodes between ‘res’ and ‘current’ and put only this ‘res’ node in the linked list.
- So we will point the next of ‘res’ to the next of ‘current’.
- Now to compute the sum of the next series -
- Move ‘current’ to the next node.
- ‘res’ to ‘current’ as ‘current’ will be pointing to the starting node of the next series.
- Update sum =0.
- Return head.
Let us understand the above approach with an example.
- Initially, ‘res’ and ‘current’ points to the head node.
- Now move the ‘current’ to the right until ‘0’ is not encountered and store the sum of all nodes in ‘sum.’
- Store this ‘sum’ value in the ‘res’. We have to remove all the nodes (5,4,0) and place only a single node with the sum value. So ‘res’ node should be linked to the node with value = 8, i.e., next to the current node.
- Move ‘res’ and ‘current’ to next of ‘current’ and repeat the above steps for the linked list’s remaining nodes.
- The resulting linked list will look like as
