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 <unordered_map>
2struct ListNode {
3 int val;
4 ListNode *next;
5 ListNode(int x) : val(x), next(nullptr) {}
6};
7
8ListNode* removeZeroSumSublists(ListNode* head) {
9 ListNode* dummy = new ListNode(0);
10 dummy->next = head;
11 std::unordered_map<int, ListNode*> prefixSumMap;
12 int sum = 0;
13 for (ListNode* cur = dummy; cur != nullptr; cur = cur->next) {
14 sum += cur->val;
15 if (prefixSumMap.find(sum) != prefixSumMap.end()) {
16 ListNode* prev = prefixSumMap[sum];
17 ListNode* temp = prev->next;
18 int p = sum;
19 while (temp != cur) {
20 p += temp->val;
21 prefixSumMap.erase(p);
22 temp = temp->next;
23 }
24 prev->next = cur->next;
25 } else {
26 prefixSumMap[sum] = cur;
27 }
28 }
29 return dummy->next;
30}The C++ implementation uses an unordered map for fast prefix sum lookups. The dummy node facilitates easy removal of nodes. Prefix sums are iterated and checked for previous occurrences to determine 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
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.