Replace The Linked List

Moderate
0/80
Average time to solve is 10m
profile
Contributed by
3 upvotes
Asked in companies
MicrosoftJosh Technology Group

Problem statement

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.
Detailed explanation ( Input/output format, Notes, Images )
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
Sample Input 1 :
2
2 5 7 0 3 4 0 -1
1 2 3 0 -1
Sample Output 1 :
14 7
6
Explanation For Sample Input 1 :
Test Case 1: In the given linked list sum of series 2, 5, 7 is 14, and the sum of series 3,4 is 7. So the modified, linked list will be 14 -> 7.

Test Case 2: The only series formed in the linked list 1,2,3 have sum = 6. Therefore modified linked list will be 6.
Sample Input 2 :
2
5 3 8 2 -1
0 6 0 4 0 -1
Sample Output 2 :
5 3 8 2
6 4
Hint

Think of traversing the linked list.

Approaches (1)
Linked List Traversal

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
Time Complexity

O( N ), where ‘ N ‘ is the number of nodes in the linked list.

 

We are traversing through the linked list once. So the time complexity is O( N ).

Space Complexity

O( 1 )

 

We have not used any extra space. So the space complexity is constant.

Code Solution
(100% EXP penalty)
Replace The Linked List
Full screen
Console