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
The C solution repeatedly scans the list, calculates a running sum, and uses a nested loop to remove nodes in zero sum sequences. This continues until no more zero sum sequences are identified.