Sponsored
Sponsored
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.
1function ListNode(val, next = null) {
2 this.val = val;
3 this.next = next;
4}
5
6function removeZeroSumSublists(head) {
7 let dummy = new ListNode(0);
8 dummy.next = head;
9 let prefixSumMap = new Map();
10 let prefix = 0;
11 for (let cur = dummy; cur !== null; cur = cur.next) {
12 prefix += cur.val;
13 if (prefixSumMap.has(prefix)) {
14 let node = prefixSumMap.get(prefix).next;
15 let sum = prefix;
16 while (node !== cur) {
17 sum += node.val;
18 prefixSumMap.delete(sum);
19 node = node.next;
20 }
21 prefixSumMap.get(prefix).next = cur.next;
22 } else {
23 prefixSumMap.set(prefix, cur);
24 }
25 }
26 return dummy.next;
27}The JavaScript implementation synchronizes the logic with other languages, utilizing a map for prefix sums and efficiently removing zero sum subsequences.
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
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.