Zero Consecutive Sum Nodes

Moderate
0/80
Average time to solve is 20m
profile
Contributed by
6 upvotes
Asked in companies
UberFlipkart limited

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

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.

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

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

Sample Input 1:

2
-2 4 -2 1 -1
1 3 5 -8 2 3 -1

Sample Output 1:

1
1 2 3

Explanation for sample input 1:

Test case 1:
The given linked list is shown below.

1

The first consecutive sequence of nodes that sum to 0 is  [-2, 4, -2].
After removing this sequence of nodes, the resulting list is [1].
Now there’s no consecutive sequence of nodes that sum to 0. Therefore the final list will be [1].

Test case 2:
The given linked list is shown below.

1

The first consecutive sequence of nodes that sum to 0 is  [3, 5, -8].
After removing this sequence of nodes, the resulting list is [1, 2, 3].
Now there’s no consecutive sequence of nodes that sum to 0. Therefore the final list will be [1, 2, 3].

Sample Input 2:

1
7 2 -2 2 3 -5 -1

Sample Output 2:

7

Explanation for sample input 2:

Test case 1:
The given linked list is shown below

1

The first consecutive sequence of nodes that sum to 0 is  [2, -2].
After removing this sequence of nodes, the resulting list is [7, 2, 3, -5].
The first consecutive sequence of nodes that sum to 0 in the current list is [2, 3, -5].
After removing this sequence of nodes, the resulting list is [7].
Now there’s no consecutive sequence of nodes that sum to 0. Therefore the final list will be [7].
Note: The first consecutive sequence that sums to 0 in the given linked list is [2, -2] and not [-2, 2] since [2, -2] occurs before [-2, 2] in the given linked list.
Hint

For each node in the linked list from left to right, check all consecutive sequences of nodes that start with this node and remove those consecutive sequences that sum to 0.

Approaches (2)
Brute Force

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.
Time Complexity

O(N ^ 2), where ‘N’ is the number of nodes in the Linked List.

 

In the worst case, we are checking all the consecutive sequences of nodes in the given linked list. There are (N * (N - 1)) different consecutive sequences of nodes.

Hence the overall time complexity will be O(N ^ 2).

Space Complexity

O(1).

 

No extra space is being used

Code Solution
(100% EXP penalty)
Zero Consecutive Sum Nodes
Full screen
Console