前缀和+链表删除
$O(n)$
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
unordered_map<int, ListNode*> hash;
auto dummy = new ListNode(0, head);
hash[0] = dummy;
int sum = 0;
while(head) {
sum += head->val;
if(hash.count(sum)) {
auto p = hash[sum];
int tmp = sum;
for(auto q = p->next; q != head; q = q->next) {
tmp += q->val;
hash.erase(tmp);
}
p->next = head->next;
}
else {
hash[sum] = head;
}
head = head->next;
}
return dummy->next;
}
};