Problem Description

Given a singly linked list, remove all consecutive sequences of nodes that sum up to zero. You must repeatedly remove zero-sum consecutive sequences until no such sequence exists in the list. The final linked list should be returned.

• Each node contains an integer value, which may be positive, negative, or zero.
• The removal process can affect the structure of the list and may need to be repeated until no zero-sum consecutive sequence remains.
• The problem guarantees that exactly one solution exists after all possible removals.
• You should not reuse or revisit any node that has already been removed.
• Input: The head node head of a singly linked list.
• Output: The head node of the modified linked list with all zero-sum consecutive sequences removed.

Thought Process

At first glance, the problem seems to require checking every possible consecutive subsequence of the linked list to see if it sums to zero, and then removing those nodes. A brute-force approach would be to try all start and end positions, sum the values, and remove nodes as needed. However, this is inefficient and can be slow for large lists.

To optimize, we can use the concept of prefix sums. If two nodes have the same prefix sum, then the nodes between them sum to zero. This is similar to finding subarrays with zero sum in an array, but applied to a linked list. By storing prefix sums and their corresponding nodes in a hash map, we can efficiently find and remove zero-sum subsequences in a single pass.

The key insight is that after removing a zero-sum sequence, we may create new zero-sum sequences that overlap or are adjacent, so we need to repeat the process until no such sequence remains. But with the prefix sum approach, we can do this in one or two passes efficiently.

Solution Approach

We use a two-pass algorithm based on prefix sums and a hash map:

1. First Pass: Build Prefix Sum Map
   • Add a dummy node before the head to handle cases where the prefix sum is zero at the start.
   • Traverse the list, maintaining a running prefix sum.
   • For each prefix sum value, store the last node where that sum occurs in a hash map.
   • If the same prefix sum appears more than once, it means the nodes in between sum to zero.
2. Second Pass: Remove Zero Sum Subsequences
   • Traverse the list again with the same prefix sum logic.
   • For each node, set its next pointer to the node after the last occurrence of the current prefix sum (from the hash map).
   • This skips over all nodes that sum to zero between these two occurrences.

We use a hash map for O(1) lookups and a dummy node to simplify edge cases. This approach ensures all zero-sum consecutive sequences are removed in O(n) time.

Example Walkthrough

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

1. First Pass (Prefix Sums):
   • Start with dummy node (value 0): prefix sum = 0
   • 1: prefix sum = 1
   • 2: prefix sum = 3
   • -3: prefix sum = 0 (again!)
   • 3: prefix sum = 3
   • 1: prefix sum = 4

   The prefix sum 0 is seen at the dummy and after -3. This means the nodes between them (1, 2, -3) sum to zero.

2. Second Pass (Remove Zero Sum):
   • Set dummy.next to node after last occurrence of prefix sum 0 (after -3). So, skip 1, 2, -3.
   • Now list is 3 -> 1.
3. Final Output:
   • The modified list is 3 -> 1.

Time and Space Complexity

• Brute-force approach:
  • Time Complexity: O(n²) or worse, since for each node, you may need to sum all subsequent nodes.
  • Space Complexity: O(1), as no extra space is used except for pointers.
• Optimized prefix sum approach:
  • Time Complexity: O(n), since we traverse the list at most twice and all hash map operations are O(1).
  • Space Complexity: O(n), for storing the prefix sums and corresponding nodes in the hash map.

The optimized approach is much faster and preferable for large lists.

Summary

The key to solving the "Remove Zero Sum Consecutive Nodes from Linked List" problem efficiently is to leverage prefix sums and a hash map. By mapping prefix sums to the most recent node where they occur, we can identify and remove zero-sum consecutive sequences in a single or double pass, resulting in an O(n) solution. This approach is both elegant and efficient, making use of linked list manipulation and hash maps for optimal performance.

Code Implementation

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prefix_sum = 0
        prefix_map = {}
        node = dummy

        # First pass: record the last occurrence of each prefix sum
        while node:
            prefix_sum += node.val
            prefix_map[prefix_sum] = node
            node = node.next

        # Second pass: remove zero-sum sequences
        prefix_sum = 0
        node = dummy
        while node:
            prefix_sum += node.val
            node.next = prefix_map[prefix_sum].next
            node = node.next

        return dummy.next
      

/**
 * 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);
        dummy->next = head;
        unordered_map<int, ListNode*> prefix_map;
        int prefix_sum = 0;
        ListNode* node = dummy;

        // First pass: record the last occurrence of each prefix sum
        while (node) {
            prefix_sum += node->val;
            prefix_map[prefix_sum] = node;
            node = node->next;
        }

        // Second pass: remove zero-sum sequences
        prefix_sum = 0;
        node = dummy;
        while (node) {
            prefix_sum += node->val;
            node->next = prefix_map[prefix_sum]->next;
            node = node->next;
        }

        ListNode* result = dummy->next;
        delete dummy;
        return result;
    }
};
      

/**
 * 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.*;
class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        Map<Integer, ListNode> prefixMap = new HashMap<>();
        int prefixSum = 0;
        ListNode node = dummy;

        // First pass: record the last occurrence of each prefix sum
        while (node != null) {
            prefixSum += node.val;
            prefixMap.put(prefixSum, node);
            node = node.next;
        }

        // Second pass: remove zero-sum sequences
        prefixSum = 0;
        node = dummy;
        while (node != null) {
            prefixSum += node.val;
            node.next = prefixMap.get(prefixSum).next;
            node = node.next;
        }

        return dummy.next;
    }
}
      

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var removeZeroSumSublists = function(head) {
    let dummy = new ListNode(0);
    dummy.next = head;
    let prefixMap = new Map();
    let prefixSum = 0;
    let node = dummy;

    // First pass: record the last occurrence of each prefix sum
    while (node) {
        prefixSum += node.val;
        prefixMap.set(prefixSum, node);
        node = node.next;
    }

    // Second pass: remove zero-sum sequences
    prefixSum = 0;
    node = dummy;
    while (node) {
        prefixSum += node.val;
        node.next = prefixMap.get(prefixSum).next;
        node = node.next;
    }

    return dummy.next;
};