Problem Description

You are given the head of a linked list. Your task is to repeatedly delete consecutive sequences of nodes whose values sum to 0 until no such sequences remain in the list.

For example, if you have a linked list 1 -> 2 -> -3 -> 3 -> 1, you can identify that the sequence 2 -> -3 sums to -1, and the sequence 3 -> -3 sums to 0. After removing the sequence that sums to 0, you would have 1 -> 2 -> 1. If there were another sequence summing to 0, you would continue removing it.

The process continues until there are no more consecutive sequences of nodes that sum to 0. You need to return the head of the modified linked list after all such removals.

The key insight is that when you find a sequence of nodes that sums to 0, you can remove all those nodes by connecting the node before the sequence directly to the node after the sequence. The solution uses prefix sums to efficiently identify these zero-sum sequences - if two positions in the linked list have the same prefix sum, it means all nodes between them sum to 0 and can be removed.

Intuition

The key observation is that if we calculate the cumulative sum (prefix sum) while traversing the linked list, and we encounter the same prefix sum value at two different positions, it means the nodes between these two positions sum to 0.

Why? Let's say at position i we have prefix sum S, and at position j (where j > i) we also have prefix sum S. This means:

• Sum from start to position i = S
• Sum from start to position j = S
• Therefore, sum from position i+1 to position j = S - S = 0

For example, consider the list 1 -> 2 -> -3 -> 3 -> 1:

• At the dummy node (before 1): prefix sum = 0
• After node 1: prefix sum = 1
• After node 2: prefix sum = 3
• After node -3: prefix sum = 0 (we've seen this before!)
• This tells us nodes between the first 0 and second 0 (which are 1 -> 2 -> -3) sum to 0

The clever part is using a hash table to store the last occurrence of each prefix sum along with its corresponding node. When we see a prefix sum that already exists, we know we can skip all nodes between the current position and the last occurrence of this sum.

By using two passes through the list:

1. First pass: Record the last node for each prefix sum value
2. Second pass: For each prefix sum, directly connect to the node after the last occurrence of that sum, effectively removing all zero-sum sequences

This approach ensures we remove all possible zero-sum consecutive sequences in just two traversals of the linked list.

Learn more about Linked List patterns.

Solution Approach

The solution uses prefix sum combined with a hash table to efficiently identify and remove zero-sum consecutive sequences.

Step 1: Setup

• Create a dummy node pointing to the head of the linked list. This helps handle edge cases where the entire list might sum to 0.
• Initialize a hash table last to store the mapping of prefix sum to the corresponding node.

Step 2: First Pass - Build Prefix Sum Map

s, cur = 0, dummy
while cur:
    s += cur.val
    last[s] = cur
    cur = cur.next

• Traverse the linked list while maintaining a running sum s.
• For each node, add its value to the cumulative sum.
• Store or update the mapping last[s] = cur, which records the last node that achieves this prefix sum.
• If the same prefix sum appears multiple times, the later occurrence overwrites the earlier one in the hash table.

Step 3: Second Pass - Remove Zero-Sum Sequences

s, cur = 0, dummy
while cur:
    s += cur.val
    cur.next = last[s].next
    cur = cur.next

• Traverse the linked list again with the same prefix sum calculation.
• For each node with prefix sum s, directly connect it to last[s].next.
• This effectively skips all nodes between the current position and the last occurrence of this prefix sum, removing any zero-sum sequences.

Why This Works:

• If nodes between position i and position j sum to 0, they will have the same prefix sum.
• In the first pass, last[s] stores the rightmost node with prefix sum s.
• In the second pass, when we encounter prefix sum s at an earlier position, we skip directly to the node after last[s], removing all intermediate nodes that sum to 0.

Example Walkthrough: For list 1 -> 2 -> -3 -> 3 -> 1:

• First pass builds: {0: dummy, 1: node(1), 3: node(2), 0: node(-3), 3: node(3), 4: node(1)}
• After overwriting: {0: node(-3), 1: node(1), 3: node(3), 4: node(1)}
• Second pass: When we reach dummy with sum 0, we connect it to last[0].next which is node(3), effectively removing 1 -> 2 -> -3.

The time complexity is O(n) where n is the number of nodes, and space complexity is O(n) for the hash table.

Example Walkthrough

Let's walk through the solution with the linked list: 1 -> 2 -> -3 -> 3 -> 1

Initial Setup:

• Create dummy node (value 0) pointing to head: dummy(0) -> 1 -> 2 -> -3 -> 3 -> 1
• Initialize empty hash table last = {}

First Pass - Building the Prefix Sum Map:

Starting from dummy, calculate prefix sums and store in hash table:

Final hash table: {0: node(-3), 1: node(1), 3: node(3), 4: node(1)}

Second Pass - Removing Zero-Sum Sequences:

Traverse again from dummy, using the hash table to skip zero-sum sequences:

1. At dummy (sum = 0):

   • Look up last[0] = node(-3)
   • Set dummy.next = last[0].next = node(-3).next = node(3)
   • This removes nodes 1 -> 2 -> -3 (they sum to 0!)

2. At node(3) (sum = 0 + 3 = 3):

   • Look up last[3] = node(3) (itself)
   • Set node(3).next = last[3].next = node(3).next = node(1)
   • No change needed (already pointing correctly)

3. At node(1) (sum = 3 + 1 = 4):

   • Look up last[4] = node(1) (itself)
   • Set node(1).next = last[4].next = node(1).next = None
   • Already at the end

Result: dummy -> 3 -> 1

The final linked list is 3 -> 1 (return dummy.next)

The beauty of this approach is that when we found prefix sum 0 at node(-3), we knew that everything from dummy to node(-3) summed to 0. By connecting dummy directly to what comes after node(-3), we removed the entire zero-sum sequence in one operation!

Solution Implementation

Time and Space Complexity

Time Complexity: O(n)

The algorithm makes two passes through the linked list:

• First pass: Traverses the entire linked list once to build the prefix sum hash map, visiting each node exactly once. This takes O(n) time.
• Second pass: Traverses the linked list again to remove zero-sum sublists by updating the next pointers based on the hash map. Each node is visited exactly once. This takes O(n) time.

Total time complexity: O(n) + O(n) = O(n), where n is the number of nodes in the linked list.

Space Complexity: O(n)

The algorithm uses additional space for:

• Hash map last: In the worst case where no sublists sum to zero, the hash map stores a unique prefix sum for each node in the linked list, requiring O(n) space.
• Variables s, cur, and dummy: These use constant space O(1).

Total space complexity: O(n), where n is the number of nodes in the linked list.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Not Using a Dummy Node

Problem: Without a dummy node, handling cases where the entire list or its beginning sums to 0 becomes complicated.

For example, if the list is 3 -> -3 -> 1, the first two nodes sum to 0 and should be removed, leaving just 1. Without a dummy node, you'd need special logic to update the head pointer.

Solution: Always use a dummy node with value 0 pointing to the head. This ensures:

• The prefix sum starts from a known state
• You never have to special-case updating the head pointer
• The dummy node acts as an anchor that won't be removed

Pitfall 2: Attempting to Remove Nodes During First Pass

Problem: Some might try to remove zero-sum sequences immediately when detected during the first traversal:

# Incorrect approach
prefix_sum_to_node = {}
current = dummy
prefix_sum = 0

while current:
    prefix_sum += current.val
    if prefix_sum in prefix_sum_to_node:
        # Try to remove nodes immediately - THIS IS WRONG
        prefix_sum_to_node[prefix_sum].next = current.next
    else:
        prefix_sum_to_node[prefix_sum] = current
    current = current.next

This fails because:

• It doesn't handle nested or overlapping zero-sum sequences correctly
• Example: 1 -> 2 -> -3 -> 3 -> -2 -> -1 has multiple overlapping zero-sum sequences
• Removing during traversal can skip nodes that should be processed

Solution: Use two separate passes:

1. First pass: Build the complete prefix sum map (later occurrences overwrite earlier ones)
2. Second pass: Use the map to reconnect nodes properly

Pitfall 3: Not Handling the Overwriting Behavior Correctly

Problem: Misunderstanding why we need to overwrite earlier occurrences of the same prefix sum in the hash map.

Consider the list: 1 -> 2 -> -3 -> 4 -> -4

• Prefix sums: 0 -> 1 -> 3 -> 0 -> 4 -> 0
• If we kept the first occurrence of prefix sum 0 (at the dummy), we'd miss removing the later zero-sum sequences

Solution: Always update prefix_sum_to_node[prefix_sum] = current even if the key exists. This ensures we keep the rightmost occurrence of each prefix sum, which allows us to remove the maximum number of nodes that form zero-sum sequences.

Pitfall 4: Forgetting to Return dummy.next Instead of dummy

Problem: Returning the dummy node itself instead of the actual head of the modified list.

# Wrong
return dummy_node

# Correct
return dummy_node.next

Solution: Always remember that the dummy node is just a helper. The actual list starts at dummy_node.next.