Sum Between Zeroes
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.

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

Question

Sum Between Zeroes

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.

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

Accepted Answer

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.

Space Complexity: O(1)Explanation:

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

Time Complexity: O(n)Explanation:

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

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

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:

Input Format:

Output Format:

Note:

Constraints:

Top Encore Capital Group Software Developer interview questions & answers

Popular interview questions of Software Developer