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.
1public class ListNode {
2 public int val;
3 public ListNode next;
4 public ListNode(int x) { val = x; }
5}
6
7public class Solution {
8 public ListNode RemoveZeroSumSublists(ListNode head) {
9 ListNode dummy = new ListNode(0);
10 dummy.next = head;
11 var prefixSumMap = new Dictionary<int, ListNode>();
12 int prefix = 0;
13 for (ListNode cur = dummy; cur != null; cur = cur.next) {
14 prefix += cur.val;
15 if (prefixSumMap.ContainsKey(prefix)) {
16 cur = prefixSumMap[prefix].next;
17 int sum = prefix + cur.val;
18 while (sum != prefix) {
19 prefixSumMap.Remove(sum);
20 cur = cur.next;
21 sum += cur.val;
22 }
23 prefixSumMap[prefix].next = cur.next;
24 } else {
25 prefixSumMap[prefix] = cur;
26 }
27 }
28 return dummy.next;
29 }
30}The C# approach uses similar logic with a dictionary to map prefix sums. Careful tracking of sums enables efficient node removal.
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.