Remove Zero Sum Consecutive Nodes from Linked List

medium linked list prefix sum hash map

Problem

Given the head of a linked list, 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.

Inputhead = [1, 2, -3, 3, 1]

Output[3, 1]

The sequence 2, -3, 1 (or 1, 2, -3) sums to 0, so those nodes are removed, leaving [3, 1].

head values (comma-separated)

def removeZeroSumSublists(head):
    dummy = ListNode(0)
    dummy.next = head
    prefix = 0
    seen = {0: dummy}
    node = dummy
    while node:
        prefix += node.val
        seen[prefix] = node
        node = node.next
    prefix = 0
    node = dummy
    while node:
        prefix += node.val
        node.next = seen[prefix].next
        node = node.next
    return dummy.next

function removeZeroSumSublists(head) {
  const dummy = new ListNode(0);
  dummy.next = head;
  let prefix = 0;
  const seen = new Map([[0, dummy]]);
  for (let node = dummy; node; node = node.next) {
    prefix += node.val;
    seen.set(prefix, node);
  }
  prefix = 0;
  for (let node = dummy; node; node = node.next) {
    prefix += node.val;
    node.next = seen.get(prefix).next;
  }
  return dummy.next;
}

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        int prefix = 0;
        Map<Integer, ListNode> seen = new HashMap<>();
        seen.put(0, dummy);
        for (ListNode node = dummy; node != null; node = node.next) {
            prefix += node.val;
            seen.put(prefix, node);
        }
        prefix = 0;
        for (ListNode node = dummy; node != null; node = node.next) {
            prefix += node.val;
            node.next = seen.get(prefix).next;
        }
        return dummy.next;
    }
}

ListNode* removeZeroSumSublists(ListNode* head) {
    ListNode* dummy = new ListNode(0);
    dummy->next = head;
    int prefix = 0;
    unordered_map<int, ListNode*> seen;
    seen[0] = dummy;
    for (ListNode* node = dummy; node; node = node->next) {
        prefix += node->val;
        seen[prefix] = node;
    }
    prefix = 0;
    for (ListNode* node = dummy; node; node = node->next) {
        prefix += node->val;
        node->next = seen[prefix]->next;
    }
    return dummy->next;
}

Explanation

The key insight is prefix sums: if the running total is the same at two points in the list, then everything between those two points adds up to zero — and can be deleted. So we track totals and look for repeats.

The prefix value is the sum of all node values from the start up to the current node. We store, in a map seen, the last node at which each prefix value occurred. Because we overwrite earlier entries, seen[p] always points to the furthest node having that running total.

In the second pass we recompute the prefix and set node.next = seen[prefix].next. If the same prefix shows up again later, this jumps the link straight past the zero-sum stretch, removing it in one move.

Example: [1, 2, -3, 3, 1]. Prefixes are 1, 3, 0, 3, 4. The value 3 appears at two nodes, so the segment between them (which sums to 0) is spliced out, leaving [3, 1].

Using a dummy head ensures a zero-sum run starting at the very beginning is handled too. Two linear passes with a hash map give an efficient solution.

Time: O(n) Space: O(n)