Zero Consecutive Sum Nodes

Posted: 19 Mar, 2021
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

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

1

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