LeetCode 1171 - Remove Zero Sum Consecutive Nodes from Linked List

LeetCode Problem 1171

Difficulty: 🟡 Medium
Topics: Hash Table, Linked List

Solution

Problem Understanding

The problem requires us to repeatedly remove consecutive nodes in a singly-linked list whose values sum to zero. The input is the head of a singly-linked list, where each node has an integer value in the range -1000 to 1000, and the list length ranges from 1 to 1000 nodes. The output should be the head of the modified linked list after all zero-sum consecutive sequences have been removed.

In simpler terms, imagine walking along the linked list and keeping track of the sum of consecutive nodes. If at any point the sum reaches zero, all nodes in that sequence should be deleted. This process is repeated until no such sequence exists. The problem guarantees a non-empty linked list and integer values, so we do not have to handle null input or non-integer nodes.

Important edge cases include sequences at the beginning or end of the list, sequences that overlap, sequences with only one node having value 0, and cases where the entire list sums to zero.

Approaches

The brute-force approach would iterate through every possible consecutive sublist and check if its sum is zero. For each node, we sum all consecutive nodes ahead of it, and if the sum is zero, we remove that sublist by adjusting pointers. This method is correct but inefficient because checking all possible sublists requires nested iteration, leading to O(n²) time complexity, which is slow for the maximum input size of 1000.

The optimal approach leverages a prefix sum with a hash map. The key insight is that if the sum of nodes from the start to node i is S and the sum to node j is also S, then the nodes between i and j sum to zero. By storing the last occurrence of each prefix sum in a hash map, we can skip directly over zero-sum sequences in one pass. This approach uses a single pass with careful pointer updates and runs in linear time.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n²)	O(1)	Check all consecutive sequences and remove zero-sum sequences iteratively
Optimal	O(n)	O(n)	Use prefix sums and a hash map to remove zero-sum sequences efficiently

Algorithm Walkthrough

1. Introduce a dummy node at the start of the linked list to simplify edge cases where the sequence starts at the head. Initialize prefix_sum = 0 and create an empty hash map sum_to_node to store the last node for each prefix sum.
2. Iterate through the linked list. For each node, update prefix_sum by adding the node's value. If prefix_sum has been seen before in sum_to_node, this indicates that all nodes between the previous occurrence and the current node sum to zero.
3. To remove zero-sum nodes, adjust the next pointer of the previous node (stored in the hash map) to skip over the zero-sum subsequence. Additionally, remove all intermediate prefix sums from the hash map to maintain correctness.
4. If prefix_sum has not been seen before, add it to the hash map with the current node as the value.
5. After traversing the list, return dummy.next as the new head of the modified list.

Why it works: The prefix sum invariant guarantees that any consecutive sequence summing to zero corresponds to a repeat in the cumulative sum. By storing the last occurrence of each prefix sum, the algorithm ensures that any zero-sum sequence is skipped in one linear pass.

Python Solution

from typing import Optional

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        prefix_sum = 0
        sum_to_node = {0: dummy}
        current = head
        
        while current:
            prefix_sum += current.val
            if prefix_sum in sum_to_node:
                prev = sum_to_node[prefix_sum]
                node = prev.next
                temp_sum = prefix_sum
                # Remove intermediate sums
                while node != current:
                    temp_sum += node.val
                    if temp_sum in sum_to_node:
                        del sum_to_node[temp_sum]
                    node = node.next
                prev.next = current.next
            else:
                sum_to_node[prefix_sum] = current
            current = current.next
        
        return dummy.next

The Python implementation follows the algorithm closely. The dummy node handles edge cases at the head. The sum_to_node hash map tracks prefix sums, and we delete intermediate sums when skipping zero-sum sequences to prevent conflicts with future nodes. The algorithm iterates through the linked list only once, achieving linear time complexity.

Go Solution

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func removeZeroSumSublists(head *ListNode) *ListNode {
    dummy := &ListNode{0, head}
    sumToNode := map[int]*ListNode{0: dummy}
    prefixSum := 0
    for current := head; current != nil; current = current.Next {
        prefixSum += current.Val
        if prev, exists := sumToNode[prefixSum]; exists {
            node := prev.Next
            tempSum := prefixSum
            for node != current {
                tempSum += node.Val
                delete(sumToNode, tempSum)
                node = node.Next
            }
            prev.Next = current.Next
        } else {
            sumToNode[prefixSum] = current
        }
    }
    return dummy.Next
}

In Go, the logic is nearly identical. Nil handling is inherent in Go pointers, and map operations are used to store prefix sums. Deleting intermediate sums ensures correctness for future iterations.

Worked Examples

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

Initial list: 1 → 2 → -3 → 3 → 1

1. prefix_sum = 1 → store {1: node1}
2. prefix_sum = 3 → store {3: node2}
3. prefix_sum = 0 → seen before at dummy → nodes 1→2→-3 sum to 0 → remove them
4. List becomes 3 → 1, prefix sums updated accordingly
5. End of list reached

Output: [3,1]

Example 2: [1,2,3,-3,4]

1. prefix_sum = 1 → store
2. prefix_sum = 3 → store
3. prefix_sum = 6 → store
4. prefix_sum = 3 → seen before at node with prefix_sum 3 → nodes 3 → -3 removed
5. List becomes 1 → 2 → 4

Output: [1,2,4]

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

1. prefix_sum = 1 → store
2. prefix_sum = 3 → store
3. prefix_sum = 6 → store
4. prefix_sum = 3 → seen before → remove 3 → -3
5. prefix_sum = 1 → seen before → remove 2 → -2
6. List becomes 1

Output: [1]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n)	Each node is visited once, and hash map operations are O(1) on average
Space	O(n)	Hash map stores prefix sums for all nodes in the worst case

The linear time complexity comes from the single traversal of the linked list, while the hash map ensures constant-time access to previously seen prefix sums. The space complexity is linear because, in the worst case, no zero-sum sequences exist and all prefix sums are stored.

Test Cases

# Basic examples
assert list_to_array(Solution().removeZeroSumSublists(array_to_list([1,2,-3,3,1]))) == [3,1]  # Example 1
assert list_to_array(Solution().removeZeroSumSublists(array_to_list([1,2,3,-3,4]))) == [1,2,4]  # Example 2
assert list_to_array(Solution().removeZeroSumSublists(array_to_list([1,2,3,-3,-2]))) == [1]  # Example 3

# Edge cases
assert list_to_array(Solution().removeZeroSumSublists(array_to_list([0]))) == []  # Single zero node
assert list_to_array(Solution().removeZeroSumSublists(array_to_list([1,-1]))) == []  # Two nodes sum to zero
assert list_to_array(Solution().removeZeroSumSublists(array_to_list([1,2,-3,3,-3,3,1]))) == [3,1]  # Overlapping sequences

# No zero-sum sequences
assert list_to_array(Solution().removeZeroSumSublists(array_to_list([1,2,3,4]))) == [1,2,3,4]

Test	Why
[1,2,-3,3,1]	Validates basic removal and overlapping sums
[1,2,3,-3,4]	Validates removal in the middle