## Similar Problems

Similar Problems not available

# Remove Zero Sum Consecutive Nodes From Linked List - Leetcode Solution

## Companies:

LeetCode: Remove Zero Sum Consecutive Nodes From Linked List Leetcode Solution

Difficulty: Medium

Topics: hash-table linked-list

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.

## Remove Zero Sum Consecutive Nodes From Linked List Solution Code

`1`