Zero Consecutive Sum Nodes

PROBLEM STATEMENT

Tanya is preparing for her coding interviews. Recently she discovered about a Singly linked list. A singly linked list is a linear data structure in which we can traverse only in one direction, i.e., from Head to Tail. It consists of several nodes where each node contains some data and a reference to the next node.

A sample Linked List

But she doesn’t like those consecutive sequences of nodes that sum to 0. As she is a beginner, she requested you to help her remove such consecutive sequences from the linked list. Formally, your task is to repeatedly remove consecutive sequences of nodes that sum to 0 and occur first in the singly linked list until there are no such sequences.

Input Format:

The first line of the input contains an integer ‘T’ representing the number of test cases.

The first line of each test case contains space-separated integers denoting the values of nodes of the Linked List. The Linked List is terminated with -1. Hence, -1 is never a node value of the Linked List.

Output Format:

For each test case, return the head of the linked-list denoting the values of nodes of the singly linked list after removing all consecutive sequences that sum to 0.

Note:

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

Constraints:

1 <= T <= 5
0 <= N <= 100
-10 ^ 3 <= data <= 10 ^ 3 and data != -1 

Where 'N' denotes the number of nodes in the given Linked List.

Time Limit: 1 sec

Approach 1

The idea here is to iterate over all the nodes in the linked list from left to right, and for each node, we will find the sum of all consecutive sequences of nodes that start with this node. Among all the consecutive sequences that start with the current node, we will remove that sequence of nodes that sums to 0 and occur first in the given linked list.

Algorithm:

Declare a dummy node, say ‘DUMMY’, and assign ‘HEAD’ in next of ‘DUMMY’, i.e., do DUMMY -> next = HEAD.
Declare a pointer, say ‘CURR_NODE’, and make ‘CURR_NODE’ = ‘DUMMY’
Run a loop until ‘CURR_NODE’ != NULL
- Create a pointer, say ‘NEXT_NODE’, and make NEXT_NODE = CURR_NODE -> next
- Declare an integer variable ‘SUM’ and initialize it with 0 and a boolean ‘FOUND’ to check if we find a consecutive sequence of nodes that SUM to 0.
- Initialize ‘FOUND’ with false.
- Run a loop until ‘NEXT_NODE’ != NULL
  - Do SUM = SUM + NEXT_NODE -> data
  - If ‘SUM’ == 0 then
    - Assign ‘NEXT_NODE -> next’ in next of ‘CURR_NODE’ i.e. do CURR_NODE -> next = NEXT_NODE -> next. As the SUM of nodes from ‘CURR_NODE -> next’ to ‘NEXT_NODE’ is 0, so we remove those nodes from the list.
    - Set ‘FOUND’ as true as we have FOUNDed a consecutive sequence that SUMs to 0.
    - Break the current loop
  - Else move the pointer of ‘NEXT_NODE’ i.e. do NEXT_NODE = NEXT_NODE -> next.
- If we did not find any consecutive sequence that SUMs to 0 and starts with ‘CURR_NODE’, we would move the pointer of ‘CURR_NODE’, i.e., do CURR_NODE = CURR_NODE -> next.
Return ‘DUMMY -> next’ as this is our required HEAD node.

Try Problem

Approach 2

The idea here is to scan the linked list from left to right and calculate the prefix sum. We make a hashmap that takes the prefix sum as a key and the corresponding node as the value. Whenever we encounter a repeated prefix sum, we find the node from the hashmap where this prefix sum occurred, say startNode, and remove all consecutive nodes from the next of startNode till the current node since they sum to 0. For

Example:

Consider that you have this Linked list: [7, 2, -2, 2, 3, -5]

Let’s calculate the prefix sum corresponding to each node in this list

Now we will iterate through the list from left to right and when we encounter a repeated prefix sum we will remove all consecutive nodes between them including the current node. As shown below:

We will repeat this process until there are no such consecutive sequences left.

Algorithm:

Declare a dummy node, say 'DUMMY', and assign ‘HEAD’ in next of 'DUMMY', i.e., do DUMMY -> NEXT = HEAD.
Declare a pointer, say ‘CURR_NODE’, and make ‘CURR_NODE’ = ‘HEAD’
Create a hashmap, say ‘HASH_MAP’, and assign ‘HASH_MAP[0]’ = 'DUMMY'
Declare an integer variable ‘PREFIX_SUM’ and initialize it with 0.
Run a loop until ‘CURR_NODE’ != NULL
- Do PREFIX_SUM = PREFIX_SUM + CURR_NODE -> data
- Check if the current prefix sum is already present in the hashmap
- If PREFIX_SUM is not present in HASH_MAP, then do:
  - Create a pointer, say ‘START_NODE’, and make START_NODE = HASH_MAP[PREFIX_SUM] -> NEXT.
  - Now remove all the consecutive nodes from ‘START_NODE’ till the ‘CURR_NODE’ as they sum to 0.
  - Declare an integer variable ‘CURR_SUM’ and initialize it with ‘PREFIX_SUM’.
  - Run a loop until ‘START_NODE’ != ‘CURR_NODE’
    - Do CURR_SUM = CURR_SUM + START_NODE -> data
    - Remove ‘CURR_SUM’ from the hashmap
    - Move the pointer of ‘START_NODE’ i.e make START_NODE = START_NODE -> NEXT
  - Assign ‘CURR_NODE -> NEXT’ in NEXT of ‘HASH_MAP[PREFIX_SUM]’ i.e. do HASH_MAP[PREFIX_SUM] -> NEXT = CURR_NODE -> NEXT to remove all consecutive nodes from ‘HASH_MAP[PREFIX_SUM] -> NEXT’ till ‘CURR_NODE’ as they sum to 0.