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.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode *next;
7};
8
9struct ListNode* removeZeroSumSublists(struct ListNode* head) {
10 struct ListNode *dummy = malloc(sizeof(struct ListNode));
11 dummy->val = 0;
12 dummy->next = head;
13 struct ListNode *cur = dummy;
14 int prefix_sum = 0;
15
16 struct ListNode **seen = calloc(1001, sizeof(struct ListNode*));
17 seen[0] = dummy;
18
19 while (cur) {
20 prefix_sum += cur->val;
21
22 if (seen[prefix_sum]) {
23 struct ListNode *node = seen[prefix_sum]->next;
24 int p = prefix_sum;
25 while (node != cur) {
26 p += node->val;
27 seen[p] = NULL;
28 node = node->next;
29 }
30 seen[prefix_sum]->next = cur->next;
31 } else {
32 seen[prefix_sum] = cur;
33 }
34
35 cur = cur->next;
36 }
37 return dummy->next;
38}This solution initializes a dummy node to handle edge cases and a hashmap to track prefix sums. As the list is traversed, prefix sums are calculated and stored. When a duplicate prefix sum is found, nodes forming a zero-sum are bypassed using the map.
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.