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.
1import java.util.HashMap;
2
3class ListNode {
4 int val;
5 ListNode next;
6 ListNode(int x) { val = x; }
7}
8
9public class Solution {
10 public ListNode removeZeroSumSublists(ListNode head) {
11 ListNode dummy = new ListNode(0);
12 dummy.next = head;
13 HashMap<Integer, ListNode> map = new HashMap<>();
14 int prefix = 0;
15 for (ListNode cur = dummy; cur != null; cur = cur.next) {
16 prefix += cur.val;
17 if (map.containsKey(prefix)) {
18 cur = map.get(prefix).next;
19 int sum = prefix + cur.val;
20 while (sum != prefix) {
21 map.remove(sum);
22 cur = cur.next;
23 sum += cur.val;
24 }
25 map.get(prefix).next = cur.next;
26 } else {
27 map.put(prefix, cur);
28 }
29 }
30 return dummy.next;
31 }
32}The Java solution employs a HashMap for tracking prefix sums and iterates through nodes using a dummy head to systematically omit zero-sum sublists.
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.