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.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.
C++
Java
Python
C#
JavaScript
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.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) worst case, due to repeated scanning of the list.
Space Complexity: O(1), only a few local variables.
| 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. |
LeetCode 1171 | Remove Zero Sum Consecutive Nodes from Linked List • leetuition • 16,699 views views
Watch 9 more video solutions →Practice Remove Zero Sum Consecutive Nodes from Linked List with our built-in code editor and test cases.
Practice on FleetCode