1171. 从链表中删去总和值为零的连续节点 (opens new window)

1.前缀和+哈希

分析：使用哈希保存以每个节点作为终点的前缀和。

• 创建哨兵节点，将前缀和0预先存入哈希中，处理链表头元素删除的情况。
• 遍历时找到相同的前缀和，则删除截取中间的子链表。注意删除时除了直接首尾相接以外，还需要将中间节点的哈希结果删除，防止后续计算的前缀和与删除的节点匹配。(实际上并不会影响最终结果)

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
            Map<Integer,ListNode> map=new HashMap<>();
            int sum=0;
            ListNode nodehead=new ListNode(0,head);
            ListNode node=head;
            map.put(0,nodehead);
            while(node!=null){
                sum+=node.val;
                if(map.containsKey(sum)){
                    ListNode start=map.get(sum),temp=start.next;
                    int del=sum;
                    while(temp!=null&&temp!=node){
                        del+=temp.val;
                        map.remove(del);
                        temp=temp.next;
                    }
                    start.next=node.next;
                }
                else{
                    map.put(sum,node);
                }
                node=node.next;
            }
            return nodehead.next;
    }
}