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
This JavaScript iteration continuously tracks and removes zero-sum sublists, ensuring thorough processing until no changes in the list occur.