# Remove Zero Sum Consecutive Nodes from Linked List
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list)
Canonical: https://scaleengineer.com/dsa/problems/remove-zero-sum-consecutive-nodes-from-linked-list
**Data structures:** Hash Table, Linked List
**Companies:** [ByteDance](https://scaleengineer.com/companies/bytedance), [josh technology](https://scaleengineer.com/companies/josh-technology)
---
## Problem
Given the `head` of a linked list, we repeatedly delete consecutive sequences of nodes that sum to `0` until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of `ListNode` objects.)

**Example 1:**

**Input:** head = [1,2,-3,3,1]
**Output:** [3,1]
**Note:** The answer [1,2,1] would also be accepted.

**Example 2:**

**Input:** head = [1,2,3,-3,4]
**Output:** [1,2,4]

**Example 3:**

**Input:** head = [1,2,3,-3,-2]
**Output:** [1]

**Constraints:**

* The given linked list will contain between `1` and `1000` nodes.
* Each node in the linked list has `-1000 <= node.val <= 1000`.

# Approaches
## Brute Force with Nested Loops
This approach uses a straightforward, brute-force method with nested loops to find and remove zero-sum consecutive subsequences. It iterates through all possible consecutive sublists, calculates their sum, and removes them if the sum is zero. This process is repeated until no such sublists can be found.
**Time:** O(N^2) - In the worst-case scenario (e.g., a list like `[1, 2, 3, ..., -sum]`), the outer loop runs N times, and for each, the inner loop might also run up to N times. This results in a quadratic time complexity. · **Space:** O(1) - We only use a few pointers (`dummy`, `outer`, `inner`) to traverse the list, so the space used is constant regardless of the list size.
**Pros:** It's relatively easy to understand the logic.; It uses constant extra space, O(1), as it only requires a few pointers.
**Cons:** The time complexity of O(N^2) is inefficient for large linked lists and will be slow.
### Explanation
The brute-force approach systematically checks every possible consecutive sequence of nodes for a zero sum. We use a `dummy` node pointing to the `head` to handle deletions at the beginning of the list gracefully.

We iterate with an `outer` pointer, which marks the node just before the start of a potential zero-sum sequence. For each position of `outer`, we use an `inner` pointer to traverse the rest of the list, calculating the sum of nodes from `outer.next` to `inner`. 

If the sum becomes zero, we've found a sequence to delete. We do this by updating the `outer.next` pointer to `inner.next`, effectively cutting the zero-sum sequence out of the list. After a deletion, we must re-evaluate from the same `outer` node, as the new connection might form another zero-sum sequence. If the inner loop finishes without finding a zero-sum sequence, we advance the `outer` pointer.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        ListNode outer = dummy;

        while (outer != null) {
            int prefixSum = 0;
            ListNode inner = outer.next;
            boolean found = false;
            while (inner != null) {
                prefixSum += inner.val;
                if (prefixSum == 0) {
                    outer.next = inner.next;
                    found = true;
                    // Break inner loop and restart scan from the same outer node
                    break; 
                }
                inner = inner.next;
            }
            
            // Only advance outer if no deletion was made from its position
            if (!found) {
                outer = outer.next;
            }
            // If a deletion was made, outer stays put to re-check from its new .next
        }

        return dummy.next;
    }
}
```
### Algorithm
1. Create a `dummy` node and set `dummy.next = head`. This simplifies handling cases where the head node is part of the sequence to be removed.
2. Initialize an `outer` pointer to the `dummy` node.
3. Loop with the `outer` pointer as long as it's not null.
4. Inside this loop, start an `inner` loop with a pointer `inner` starting from `outer.next` and a `sum` initialized to 0.
5. The `inner` loop traverses the rest of the list, accumulating the sum of node values.
6. If at any point `sum` becomes 0, it means the consecutive sequence of nodes from `outer.next` to `inner` sums to zero.
7. Upon finding such a sequence, we remove it by setting `outer.next = inner.next`. This effectively bypasses all the nodes in the zero-sum sequence.
8. After a deletion, we break the `inner` loop and the `outer` loop continues from the same `outer` node, but with its `next` pointer updated. This is crucial because the deletion might have formed a new zero-sum sequence with earlier nodes.
9. If the `inner` loop completes without the `sum` ever becoming 0, it means no zero-sum sequence starts at `outer.next`. In this case, we can safely advance `outer` to its next node.
10. Finally, return `dummy.next`, which will be the head of the modified list.

## Single Pass with Prefix Sum and Hash Map
A more efficient approach uses a hash map to store the prefix sums encountered while traversing the linked list. The key idea is that if a prefix sum `S` is seen at node `i` and again at node `j`, the sum of the elements between `i` and `j` is zero. This allows for faster detection of zero-sum sequences. This specific version accomplishes the task in a single pass.
**Time:** O(N) - Although there is a nested loop to clean the map, each node is added to and removed from the map at most once. This leads to an amortized time complexity of O(N). · **Space:** O(N) - In the worst-case scenario where all prefix sums are unique, the hash map will store an entry for each of the N nodes.
**Pros:** Highly efficient with an O(N) time complexity.; Processes the list in a single pass, which can be faster in practice than a two-pass approach.
**Cons:** The logic for cleaning up the hash map adds complexity to the implementation.; While amortized O(N), the operations within the loop can be costly if long zero-sum sequences are found repeatedly.
### Explanation
This method traverses the list just once, building up a map of prefix sums to nodes as it goes. We use a `dummy` node to anchor the process, with an initial prefix sum of 0 pointing to it.

As we iterate through the list, we calculate the cumulative `prefixSum`. If we encounter a `prefixSum` that we've seen before, we know the nodes between the previous occurrence and the current node form a zero-sum sequence. 

The main challenge in this one-pass approach is maintaining the correctness of the map. When we find a zero-sum sequence and are about to delete it, we must also remove the map entries corresponding to all the nodes being deleted. This is because their prefix sums are calculated based on a path that is now being removed. After cleaning the stale entries from the map, we can safely bypass the sequence by updating the `next` pointer of the previous node.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
import java.util.HashMap;
import java.util.Map;

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        Map<Integer, ListNode> map = new HashMap<>();
        int prefixSum = 0;
        
        // First, put the initial state in the map
        map.put(0, dummy);

        ListNode current = head;
        while (current != null) {
            prefixSum += current.val;
            if (map.containsKey(prefixSum)) {
                ListNode prev = map.get(prefixSum);
                ListNode toRemove = prev.next;
                int p = prefixSum + toRemove.val;
                // Remove stale entries from the map
                while (p != prefixSum) {
                    map.remove(p);
                    toRemove = toRemove.next;
                    p += toRemove.val;
                }
                // Bypass the zero-sum sequence
                prev.next = current.next;
            } else {
                map.put(prefixSum, current);
            }
            current = current.next;
        }
        
        return dummy.next;
    }
}
```
### Algorithm
1. Create a `dummy` node with value 0 and point its `next` to the `head`.
2. Initialize a `HashMap<Integer, ListNode>` to store prefix sums and the corresponding nodes where they occur. Put an initial entry `(0, dummy)` into the map.
3. Initialize `prefixSum = 0`.
4. Traverse the list with a `current` pointer, starting from the `dummy` node.
5. In each step, update the `prefixSum` by adding the `current` node's value.
6. Check if the new `prefixSum` already exists in the map. 
   a. If it does, it means the sublist between the node previously stored for this `prefixSum` (`prev = map.get(prefixSum)`) and the `current` node sums to zero.
   b. Before deleting this sublist, we must clean the map. We iterate from `prev.next` to `current`, removing the map entries for all the intermediate nodes, as their prefix sums are now invalid.
   c. After cleaning the map, we perform the deletion by setting `prev.next = current.next`.
   d. If the `prefixSum` is not in the map, we add a new entry: `map.put(prefixSum, current)`.
7. Continue this process until the end of the list is reached.
8. Return `dummy.next`.

## Two Passes with Prefix Sum and Hash Map
This optimal approach also uses a hash map and the concept of prefix sums but simplifies the logic by breaking the problem into two separate passes. The first pass is dedicated to building a map of prefix sums to nodes, and the second pass uses this map to efficiently rewire the linked list and remove all zero-sum sequences at once.
**Time:** O(N) - The algorithm consists of two sequential passes over the linked list. Each pass takes O(N) time. The total time complexity is O(N) + O(N) = O(N). · **Space:** O(N) - The hash map can store up to N+1 entries (for N nodes plus the dummy node) in the worst case where all prefix sums are unique.
**Pros:** Optimal O(N) time complexity.; The logic is cleaner and more straightforward than the one-pass approach, as it separates the discovery phase (pass 1) from the modification phase (pass 2).; It is generally easier to implement correctly and debug.
**Cons:** Requires two full traversals of the linked list, which might have slightly more overhead than a one-pass solution.
### Explanation
This method is both efficient and easier to reason about compared to the single-pass version.

**First Pass:** We traverse the entire linked list once to populate a hash map. The map stores key-value pairs of `(prefixSum, node)`. When we calculate the prefix sum at each node, we place it in the map. If a prefix sum value already exists, we overwrite it. This is a key step: by the end of the pass, the map will only contain the *last* node at which each prefix sum occurred. This elegantly handles nested or overlapping zero-sum sequences, as it automatically finds the largest possible sequence to remove.

**Second Pass:** We traverse the list again, starting from the `dummy` node. For each node `current`, we calculate its prefix sum. We then look up this sum in our map. The node retrieved from the map, `map.get(prefixSum)`, is the end of a potential zero-sum sequence that starts right after `current`. We can therefore perform the deletion by simply setting `current.next` to `map.get(prefixSum).next`. This single assignment correctly skips all intermediate nodes. We repeat this for every node in our second traversal, ensuring all necessary connections are made.

```java
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
import java.util.HashMap;
import java.util.Map;

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0, head);
        Map<Integer, ListNode> map = new HashMap<>();
        int prefixSum = 0;

        // First pass: build the map of prefix sums to the last node seen with that sum
        ListNode current = dummy;
        while (current != null) {
            prefixSum += current.val;
            map.put(prefixSum, current);
            current = current.next;
        }

        // Second pass: rewire the list
        prefixSum = 0;
        current = dummy;
        while (current != null) {
            prefixSum += current.val;
            // Connect current node to the node after the last occurrence of its prefix sum
            current.next = map.get(prefixSum).next;
            current = current.next;
        }

        return dummy.next;
    }
}
```
### Algorithm
1. **First Pass: Build Prefix Sum Map**
   a. Create a `dummy` node with value 0 and set `dummy.next = head`.
   b. Create a `HashMap<Integer, ListNode>` to store the last seen node for each prefix sum.
   c. Initialize `prefixSum = 0` and a pointer `current = dummy`.
   d. Iterate through the list from `dummy` to the end. In each step, update `prefixSum += current.val` and store the mapping in the hash map: `map.put(prefixSum, current)`. If a prefix sum is encountered more than once, its entry in the map will be overwritten with the latest node. This ensures the map holds the final occurrence of each prefix sum.

2. **Second Pass: Rewire the Linked List**
   a. Reset `prefixSum = 0` and `current = dummy`.
   b. Iterate through the list again from `dummy` to the end.
   c. In each step, update `prefixSum += current.val`.
   d. Use the map built in the first pass to find the correct next node. The sublist between `current` and `map.get(prefixSum)` sums to zero. Therefore, we can skip this entire sublist by setting `current.next = map.get(prefixSum).next`.
   e. Advance `current` to its (potentially new) next node.

3. Return `dummy.next`.

# Solutions
### Java

```java
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode removeZeroSumSublists ( ListNode head ) { ListNode dummy = new ListNode ( 0 , head ); Map < Integer , ListNode > last = new HashMap <>(); int s = 0 ; ListNode cur = dummy ; while ( cur != null ) { s += cur . val ; last . put ( s , cur ); cur = cur . next ; } s = 0 ; cur = dummy ; while ( cur != null ) { s += cur . val ; cur . next = last . get ( s ). next ; cur = cur . next ; } return dummy . next ; } }
```

### CPP

```cpp
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode * removeZeroSumSublists ( ListNode * head ) { ListNode * dummy = new ListNode ( 0 , head ); unordered_map < int , ListNode *> last ; ListNode * cur = dummy ; int s = 0 ; while ( cur ) { s += cur -> val ; last [ s ] = cur ; cur = cur -> next ; } s = 0 ; cur = dummy ; while ( cur ) { s += cur -> val ; cur -> next = last [ s ] -> next ; cur = cur -> next ; } return dummy -> next ; } };
```

### Python

```python
# Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution : def removeZeroSumSublists ( self , head : Optional [ ListNode ]) -> Optional [ ListNode ]: dummy = ListNode ( next = head ) last = {} s , cur = 0 , dummy while cur : s += cur . val last [ s ] = cur cur = cur . next s , cur = 0 , dummy while cur : s += cur . val cur . next = last [ s ]. next cur = cur . next return dummy . next
```