难度中等
给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头节点。
你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）
示例 1：
输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。示例 2：
输入：head = [1,2,3,-3,4]
输出：[1,2,4]示例 3：
输入：head = [1,2,3,-3,-2]
输出：[1]1、暴力解法：
如果要遍历到每一组求和等于0的连续结点，可以从每个结点出发，遍历它的后缀和，如果它的后缀和等于0了，说明当前遍历的起始结点到令后缀和等于0的这些结点是一组求和等于0的连续结点，应当删除掉，但是不要delete,因为经过测试如果delete掉头结点后 Leetcode会报错，猜测可能和 Leetcode 的测试用例的链表实现有关系，所以删除掉的方法就是cur->next = search->next,这里cur是起始结点的前一个结点，search是使前缀和等于0的结点。
为了避免头结点删除后返回新的头结点的困难，同时可以和起始结点的前一个结点这一想法相配合，可以增加一个哨兵结点 newhead.
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* removeZeroSumSublists(ListNode* head) {
//创建一个头节点
ListNode* newhead = new ListNode(0, head);
//创建一个cur用来作为每次遍历的起始节点
ListNode* cur = newhead;
while(cur != nullptr)
{
int sum = 0;
ListNode* search = cur->next;
while(search != nullptr)
{
sum += search->val;
if(sum == 0)
{
cur->next = search->next;
}
search = search->next;
}
cur = cur->next;
}
ListNode* tmp = newhead->next;
delete newhead;
return tmp;
}
};2、哈希+前缀和
注意这里的细节就是哨兵节点要设为0，并且每次从哨兵节点出发遍历，自己走一遍就知道为什么！
class Solution
{
public:
ListNode* removeZeroSumSublists(ListNode* head)
{
// **定义虚拟节点：「链表问题的一般做法」**
ListNode* dummy = new ListNode(0, head);
// **前缀和哈希表：记录前缀和以及该前缀和的最后一个节点**
unordered_map<int, ListNode*> location;
// 前缀和：sum 记录
int sum = 0;
// **NB：从 dummy 开始遍历，防止需要删除头节点的情况**
// 「NO.1」构建前缀和哈希表
for (ListNode* curr = dummy; curr != nullptr; curr = curr->next) {
sum += curr->val; // 前缀和
location[sum] = curr;
}
// 「NO.2」删除连续和为零的连续节点
sum = 0;
for (ListNode* curr = dummy; curr != nullptr; curr = curr->next) {
sum += curr->val; // 前缀和
curr->next = location[sum]->next;
}
// 返回虚拟节点的下一个节点「链表问题的一般解法」
return dummy->next;
}
};