Zero Consecutive Sum Nodes

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.

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.