Remove Zero Sum Consecutive Nodes — Prefix Sum HashMap Explained

Problem Statement#

LeetCode 1171 — Remove Zero Sum Consecutive Nodes from Linked List Difficulty: Medium | Pattern: Prefix Sum + HashMap

Given the head of a linked list, repeatedly delete consecutive sequences of nodes that sum to 0 until no such sequences remain. Return the head of the final linked list.

Constraints:

• Number of nodes: 1 <= n <= 1000
• -1000 <= Node.val <= 1000

Example 1:

Input:  [1, 2, -3, 3, 1]
Output: [3, 1]   (or [1, 2, 1] — both are valid)
Explanation: [1, 2, -3] sums to 0. Remove it. Resulting [3, 1].

Example 2:

Input:  [1, 2, 3, -3, 4]
Output: [1, 2, 4]
Explanation: [3, -3] sums to 0. Remove it.

Example 3:

Input:  [0, 1]
Output: [1]
Explanation: [0] alone sums to 0. Remove it.

Why This Problem Matters#

This is one of the best examples of how the classic prefix sum technique — usually associated with arrays — transfers beautifully to linked lists. Google, Amazon, and Bloomberg have been known to use this problem as a filter question that separates candidates with strong algorithmic intuition from those who only know surface-level patterns.

The naive approach is to repeatedly scan the list looking for zero-sum runs — an O(n²) or worse approach that falls apart for large inputs. The optimal solution completes the entire task in two O(n) passes by leveraging a hashmap of prefix sums, the same insight that solves "Subarray Sum Equals K" (LC 560).

Understanding this problem also strengthens your intuition about prefix sums as a general tool. If you have seen two occurrences of the same prefix sum, everything between them sums to zero — this is the core theorem behind both the array and linked list variants.

Interviewers at Google and Amazon frequently use this problem in mid-level interviews because it requires you to (a) recognize the prefix sum pattern, (b) adapt it to a linked list structure, and (c) correctly handle repeated removals without scanning the list multiple times.

The Core Insight#

The key theorem: If you compute prefix sums as you traverse the list and you encounter the same prefix sum twice, then all nodes between the first and second occurrence of that prefix sum have a combined value of zero — they must be removed.

The two-pass algorithm:

1. Pass 1: Traverse the list computing running prefix sums. For each prefix sum, record the last node where that prefix sum was seen in a hashmap.
2. Pass 2: Traverse the list again. For each prefix sum, look up the hashmap and make the current node's next pointer jump directly to the node after the stored node. This skips over the entire zero-sum sequence in one step.

Using a dummy head node simplifies the boundary case where the zero-sum segment starts at the very first node.

Visual Dry Run#

Input: [1, 2, -3, 3, 1]

Pass 1 — build prefix sum map (last occurrence):

Pass 2 — relink:

Result: [3, 1]

Solution (Optimal)#

from typing import Optional
 
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
 
def removeZeroSumSublists(head: Optional[ListNode]) -> Optional[ListNode]:
    dummy = ListNode(0)
    dummy.next = head
 
    # Pass 1: Record the last node at each prefix sum
    prefix_map = {0: dummy}
    prefix = 0
    curr = head
    while curr:
        prefix += curr.val
        prefix_map[prefix] = curr  # overwrite with last occurrence
        curr = curr.next
 
    # Pass 2: Relink nodes, skipping zero-sum sequences
    prefix = 0
    curr = dummy
    while curr:
        prefix += curr.val
        # Jump to the node after the last node with this prefix sum
        curr.next = prefix_map[prefix].next
        curr = curr.next
 
    return dummy.next

function removeZeroSumSublists(head) {
    const dummy = { val: 0, next: head };
 
    // Pass 1: Record last occurrence of each prefix sum
    const prefixMap = new Map();
    prefixMap.set(0, dummy);
    let prefix = 0;
    let curr = head;
    while (curr) {
        prefix += curr.val;
        prefixMap.set(prefix, curr); // overwrite with last occurrence
        curr = curr.next;
    }
 
    // Pass 2: Relink, skipping zero-sum segments
    prefix = 0;
    curr = dummy;
    while (curr) {
        prefix += curr.val;
        curr.next = prefixMap.get(prefix).next;
        curr = curr.next;
    }
 
    return dummy.next;
}

Complexity:

Common Mistakes#

1. Using first occurrence instead of last in the map: Pass 1 must store the last node for each prefix sum. If you store the first, the relinking in Pass 2 only removes the innermost zero-sum segment, not all of them.
2. Forgetting the dummy node in the prefix map: Initialize the map with {0: dummy}. This handles the case where a zero-sum sequence starts from the very first node.
3. Not including dummy in Pass 2: The second traversal must start from dummy, not from head, so that the dummy's next pointer can be corrected if the first segment is zero-sum.
4. Attempting a single pass: A single pass is possible but significantly more complex. In an interview, the clean two-pass approach is easier to explain, verify, and defend.
5. Confusion with repeated zeros: A single node with value 0 has a prefix sum equal to the prefix sum just before it — it will be correctly removed by the relinking step.

Interview Tips#

• Name the analogy: "This is the same prefix sum theorem as 'Subarray Sum Equals K' — same prefix sum twice means zero sum in between."
• Explain why two passes: The first pass records the last occurrence of each prefix sum so that all overlapping zero-sum segments are collapsed correctly.
• Draw the map updates: Walking through how the map gets overwritten in Pass 1 makes the algorithm transparent to the interviewer.
• Start with the dummy node: Mention it immediately — it shows you are thinking about edge cases.
• Verify with example 3: The input [0, 1] is a great minimal test case. The zero node has prefix sum 0, which matches the dummy's prefix sum 0, so the dummy's next jumps to node(1).

Follow-up Questions#

1. Can you solve it in one pass? Yes, but it requires more bookkeeping. Discuss the tradeoff between code complexity and pass count.
2. What if values can be very large? The hashmap key space grows but the O(n) bound holds.
3. LeetCode 560 — Subarray Sum Equals K: Same prefix sum theorem on arrays. Can you solve that next?
4. What if the entire list sums to zero? The dummy's next pointer gets set to null — the function returns null (empty list).
5. How does this differ from removing a single zero-sum subarray? This problem must remove all zero-sum consecutive sequences, not just the first one found.

Key Takeaways#

• The prefix sum theorem applies to linked lists: if the same prefix sum appears twice, all nodes between those two positions sum to zero.
• Pass 1 builds a hashmap of prefix sums to their last node. Pass 2 relinks nodes using that map to skip zero-sum segments.
• Always initialize the map with {0: dummy} to handle zero-sum sequences starting from the head.
• Two O(n) passes give an overall O(n) time and O(n) space solution.
• This problem directly combines linked list manipulation with the classic prefix sum pattern — a combination that appears in Google and Amazon interviews.
• Mastering this problem also strengthens your intuition for LC 560, LC 974, and any "contiguous subarray sum" variant.