Remove Zero Sum Consecutive Nodes from Linked List - Solution & Explanation
Problem Statement
Given the head of a linked list, we 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.
(Note that in the examples below, all sequences are serializations of ListNode objects.)
Example 1:
Input: head = [1,2,-3,3,1] Output: [3,1] Note: The answer [1,2,1] would also be accepted.
Example 2:
Input: head = [1,2,3,-3,4] Output: [1,2,4]
Example 3:
Input: head = [1,2,3,-3,-2] Output: [1]
Constraints:
- The given linked list will contain between
1and1000nodes. - Each node in the linked list has
-1000 <= node.val <= 1000.
Approach Overview
Problem Overview: You are given the head of a linked list. If any consecutive sequence of nodes sums to 0, that entire sequence should be removed from the list. This removal can create new zero-sum sequences, so the process continues until no such segment exists.
Approach 1: Iterative Node Skipping (O(n²) time, O(1) space)
This approach repeatedly scans the list and checks every starting node to see whether a future sequence sums to zero. For each node, maintain a running sum while iterating forward. If the sum becomes 0, skip the entire range by adjusting the previous node’s next pointer. Because each node may trigger another forward scan, the algorithm can degrade to O(n²) time. The advantage is minimal memory usage since it only uses pointers and running sums without extra data structures. This approach helps you understand the mechanics of node removal in a linked list.
Approach 2: Prefix Sum Hash Map (O(n) time, O(n) space)
The optimal solution uses the prefix sum idea with a hash table. Traverse the list while maintaining a running prefix sum. If the same prefix sum appears twice, the nodes between those two positions must sum to zero. Store each prefix sum in a hash map pointing to the latest node where that sum appears. In a second pass, recompute prefix sums and update pointers so that each node skips directly to the next valid node stored in the map. This effectively removes all zero-sum segments in one sweep.
The key insight: identical prefix sums indicate a zero-sum range between them. Using a hash lookup reduces detection of these ranges to constant time, making the full traversal O(n). This pattern is common in problems involving cumulative sums and range detection, often discussed alongside hash map or linked list manipulations.
Recommended for interviews: The prefix sum + hash map approach is what most interviewers expect. The iterative method demonstrates that you understand linked list traversal and pointer manipulation, but the prefix-sum optimization shows stronger algorithmic thinking and familiarity with hash-based lookups that reduce quadratic scans to linear time.
Approach 1: Prefix Sum Hash Map
This approach uses a hashmap to record prefix sums while iterating through the linked list. When a prefix sum is repeated, it indicates that the nodes between the occurrences of the prefix sum form a zero-sum sequence.
This solution initializes a dummy node to handle edge cases and a hashmap to track prefix sums. As the list is traversed, prefix sums are calculated and stored. When a duplicate prefix sum is found, nodes forming a zero-sum are bypassed using the map.
Complexity
Time Complexity: O(n) where n is the number of nodes. Each node is visited at most twice.
Space Complexity: O(n) for the hashmap storing prefix sums.
Approach 2: Iterative Node Skipping
This approach keeps processing the list until no zero-sum sublists can be found. This involves iterative rescanning of the list and skipping nodes accordingly.
The C solution repeatedly scans the list, calculates a running sum, and uses a nested loop to remove nodes in zero sum sequences. This continues until no more zero sum sequences are identified.
Complexity
Time Complexity: O(n^2) worst case, due to repeated scanning of the list.
Space Complexity: O(1), only a few local variables.
Approach 3: Prefix Sum + Hash Table
If two prefix sums of the linked list are equal, it means that the sum of the continuous node sequence between the two prefix sums is 0, so we can remove this part of the continuous nodes.
We first traverse the linked list and use a hash table last to record the prefix sum and the corresponding linked list node. For the same prefix sum s, the later node overwrites the previous node.
Next, we traverse the linked list again. If the current node cur has a prefix sum s that appears in last, it means that the sum of all nodes between cur and last[s] is 0, so we directly modify the pointer of cur to last[s].next, which removes this part of the continuous nodes with a sum of 0. We continue to traverse and delete all continuous nodes with a sum of 0.
Finally, we return the head node of the linked list dummy.next.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the linked list.
Complexity Comparison
| Approach | Complexity |
|---|---|
| Prefix Sum Hash Map | Time Complexity: O(n) where n is the number of nodes. Each node is visited at most twice. Space Complexity: O(n) for the hashmap storing prefix sums. |
| Iterative Node Skipping | Time Complexity: O(n^2) worst case, due to repeated scanning of the list. Space Complexity: O(1), only a few local variables. |
| Prefix Sum + Hash Table | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Node Skipping | O(n²) | O(1) | Useful for understanding pointer manipulation and when minimizing memory usage matters |
| Prefix Sum Hash Map | O(n) | O(n) | Best general solution. Detects zero-sum segments quickly using prefix sums and hash lookups |
Video Solution
Remove Zero Sum Consecutive Nodes from Linked List | Made Super Easy | Leetcode-1171 • codestorywithMIK • 21,477 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Remove Zero Sum Consecutive Nodes from Linked List easy or hard?
Remove Zero Sum Consecutive Nodes from Linked List Python/Java solution
How to solve Remove Zero Sum Consecutive Nodes from Linked List in O(n)?
What is the best approach for Remove Zero Sum Consecutive Nodes from Linked List?
Is Remove Zero Sum Consecutive Nodes from Linked List asked at Google/Amazon/Meta?
What data structure is used in Remove Zero Sum Consecutive Nodes from Linked List?
What is the time complexity of Remove Zero Sum Consecutive Nodes from Linked List?
Ready to solve this problem?
Practice Remove Zero Sum Consecutive Nodes from Linked List with our built-in code editor and test cases.
Practice on FleetCodeProblem Info
Table of Contents
Practice this problem
Open in Editor