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.The key idea in #1171 Remove Zero Sum Consecutive Nodes from Linked List is recognizing that a sequence of nodes sums to zero when two positions in the list have the same prefix sum. As you traverse the linked list, maintain a running sum and store it in a hash table mapping each prefix sum to the most recent node where it appears.
If the same prefix sum appears again, it means the nodes between those two positions sum to 0. You can remove that entire segment by adjusting pointers to skip those nodes. A common strategy uses a two-pass traversal: the first pass records prefix sums in a map, and the second pass reconnects nodes using the stored references to eliminate zero-sum segments.
This approach efficiently handles overlapping zero-sum ranges and ensures the final list contains only nodes that cannot form a zero-sum consecutive sequence. The solution runs in linear time with additional space for the hash map.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Prefix Sum with Hash Map (Two Pass) | O(n) | O(n) |
leetuition
Use these hints if you're stuck. Try solving on your own first.
Convert the linked list into an array.
While you can find a non-empty subarray with sum = 0, erase it.
Convert the array into a linked list.
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.
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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode
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.
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.
Time Complexity: O(n^2) worst case, due to repeated scanning of the list.
Space Complexity: O(1), only a few local variables.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums help track the cumulative sum from the start of the list to the current node. If the same sum appears twice, the nodes between them must sum to zero, making it easy to identify and remove that section.
Yes, variations of this problem are common in technical interviews at large tech companies. It tests understanding of prefix sums, hash maps, and pointer manipulation in linked lists.
A hash map is the most effective data structure for this problem. It stores prefix sums as keys and the latest node where the sum appears, allowing quick detection and removal of zero-sum consecutive segments.
The optimal approach uses a prefix sum technique combined with a hash map. By storing prefix sums and their corresponding nodes, you can detect when a sublist sums to zero and remove it efficiently in linear time.
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.