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 public int val;
public ListNode next;
public ListNode(int x) { val = x; }
}
public class Solution {
public ListNode RemoveZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0);
dummy.next = head;
bool removed = true;
while (removed) {
ListNode cur = dummy;
int sum = 0;
removed = false;
while (cur.next != null) {
sum += cur.next.val;
if (sum == 0) {
cur.next = cur.next.next;
removed = true;
} else {
cur = cur.next;
}
}
}
return dummy.next;
}
}The solution repeatedly scans the list, tracking sums, and bypasses nodes forming zero-sum sequences, continuing until no more can be found.