Remove Zero Sum Consecutive Nodes from Linked List

To solve this efficiently, I would leverage the concept of prefix sums combined with a hash map to achieve O(N) time complexity. The core insight is that if we encounter the same cumulative sum at two different nodes, the sequence of nodes between them must sum to zero. First, I would create a dummy node pointing to the head to handle edge cases where the head itself is part of a zero-sum sequence. Then, I would iterate through the list once, maintaining a running cumulative sum. For each node, I would store the mapping from the current cumulative sum to that node in a hash map. If we encounter a sum that already exists in our map, it indicates a zero-sum subarray between the previous occurrence and the current node. However, since we need to remove these nodes, a standard one-pass deletion is tricky because removing nodes affects future sums. Therefore, I prefer a two-pass approach. In the first pass, we populate the map with all cumulative sums and their corresponding nodes. In the second pass, we traverse again; whenever we see a cumulative sum that has been seen before, we update the next pointer of the previous node to skip directly to the node after the current one, effectively deleting the zero-sum segment. This ensures we handle nested or overlapping zero-sum sequences correctly without re-scanning the list repeatedly.