Sum Between Zeroes

Easy

0/40

Average time to solve is 20m

Contributed by

34 upvotes

Asked in companies

Problem statement

You are given a Singly Linked List which contains a series of integers separated by ‘0’.

Between two zeroes, you have to merge all the nodes lying between them into a single node which contains the sum of all the merged nodes. You have to perform this in place.

Note:

It is guaranteed that there will be no two consecutive zeroes, and there will always be a zero at the beginning and end of the linked list.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line of input contains the elements of the singly linked list separated by a single space. The -1 indicates the end of the singly linked list and hence, would never be a list element.

Output Format:

The first and the only output line contains the integers present in the linked list after all the merging operations have been performed.

Note:

You do not need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

3 <= N <= 10^5
0 <= VAL <= 10^3

Where 'VAL' represents the integers present in the list.

Time limit: 1 sec

Sample Input 1:

0 1 2 3 0 4 5 0 6 0 -1

Sample Output 1:

6 9 6 -1

Explanation Of Sample Input1:

The given linked list is:
0 -> 1 -> 2 -> 3 -> 0 -> 4 -> 5 -> 0 -> 6 -> 0 -> null
Then, the linked list is converted to:
6 -> 9 -> 6 -> null
Taking 0s as the start and end in reference to a sequence, we can see that there are 3 sequences. They are:
 1. 1 -> 2 -> 3, which sum to 6
 2. 4 -> 5, which sum to 9
 3. 6, which sum to 6 only

Sample Input 2:

0 1 2 4 8 16 0 -1

Sample Output 2:

31 -1

Hint 1

Let’s not think of merging nodes, but rather transferring their contents into a single node. Can you think of an approach to do this by maintaining two pointers?

Approaches (1)

Approach 1

Two Pointer Approach

Let us initialize two pointers, newHead and newTail, with NULL (These will be the head and tail of the final list). Now traverse the given list. Ignore the first zero. Now, as you encounter non-zero nodes, add their values in a variable called ‘sum’. As soon as you encounter a node with data 0, change that node's value to ‘sum’, and

If newHead is NULL, this node becomes the new head and tail of the list
If newHead is not NULL, then connect this node with the tail of the list and assign it to be the new tail

Follow this algorithm for the rest of the list.

Note that we are not creating a new list, because we don’t create new nodes, we simply change the values of existing nodes and modify their connections.

Time Complexity

O(N), where N is the size of the linked list.

Traversing the linked list once takes O(N) time.

Space Complexity

O(1), as constant extra space is required.

(100% EXP penalty)

Sum Between Zeroes

Console