Problem Statement:

Given a linked list, remove all consecutive nodes that sum up to 0.

Example: Input: 1 -> 2 -> -3 -> 3 -> 1 Output: 1 -> 2 -> 1

Approach:

We can solve this problem by using a Hash Table (Dictionary in Python).

Firstly, we will traverse the linked list and calculate the sum of each node and store it in the dictionary with key as the sum and value as the node index.

If we encounter a sum which is already present in the dictionary, we will traverse from the last node index to the current index. And, we will remove all the nodes whose sum is zero.

We will also add the current node sum to the dictionary.

Coding Solution:

class Solution: def removeZeroSumSublists(self, head: ListNode) -> ListNode:

Creating a dummy node

dummy = ListNode()

Pointing the next of the dummy to the head

dummy.next = head

Creating a dictionary

d = {}

Initializing the sum as zero

sum = 0

Looping through the list

node = dummy while node: sum += node.val

# If the sum is already in the dictionary,
# remove all the nodes from the last node upto the current node
if sum in d:
    prev = d[sum].next
    temp = sum
    while prev != node:
        temp += prev.val
        del d[temp]
        prev = prev.next

    # Connecting the last node to the current node
    d[sum].next = node.next

else:
    # Adding the sum and node to the dictionary
    d[sum] = node

# Traversing through the list
node = node.next

Returning the head of the modified list

return dummy.next

Time Complexity: O(n), where n is the length of the linked list. Space Complexity: O(n), the space used by the dictionary is the same as the number of nodes in the linked list.

1