Watch 10 video solutions for Remove Zero Sum Consecutive Nodes from Linked List, a medium level problem involving Hash Table, Linked List. This walkthrough by codestorywithMIK has 20,046 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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:
1 and 1000 nodes.-1000 <= node.val <= 1000.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 | 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 |