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

题目来源于力扣题库，题目链接：LC1171.从链表中删去总和值为零的连续节点

Q：给你一个链表的头节点 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]

A：分析：通过阅读题目，我们可以得到的较为重要的信息就是“反复删去”、“总和为0”、“连续节点组成的序列”、“直到不存在为止”这类的关键字眼，那么我们接下来构思解决方案的时候肯定是要围绕着解决这几个关键字来进行的。

　　首先，碰到链表类的题目，大概率是要手动去创建一个哑结点的，并将其next指针指向头结点。本题给了一个头结点且又是涉及到删除操作，所以创建哑结点（dummyNode）刻不容缓；其次，反复删除一定是要设计到一个循环的，从首至尾，并非找到一组总和值为0的连续节点组成的序列就结束了，而是要不断的寻找，直到不存在这样的序列为止。谈到“这样的序列”，我们也要想一想，总和为0的连续节点组成的序列会有哪些情况？第一种情况，单个节点的val就是0的；第二种情况多个（大于1）连续节点的val之和为0的。最后，一个较为重要的问题就是如何去求连续节点组成序列的“总和”。我们可以举个例子来看看用什么方法，现假设一共有5个节点，即[Node1(1, Node2), Node2(2, Node3), Node3(1, Node4), Node4(-3, Node5), Node5(10, Null)]，这里我们定义一个节点为Node(val, next)的形式，则很显然，中间的三个连续节点Node2、Node3和Node4的和是为0的，所以接下来要做的就是将移动Node1的next指针，使其指向Node5，即可完成删除。但是，如何判断呢？怎么才能知道从Node2到Node5的和值为0呢？“前缀和”（前缀和指一个数组的某下标之前的所有数组元素的和（包含其自身））可以去解决这个问题，因为前缀和是具有记忆作用的，想象一下，当两个节点的前缀和相同，那么是不是就说明了存在连续的和为0的节点序列了呀。

　　现举例模拟上述思想，我们使用了哈希表来存储key为前缀和prefix，value为节点Node，初始化一个哑结点为dummyNode，并将其值val设置为0。我们还是利用上述给出的那个链表，并在其基础上加上我们新创建的哑结点，则链表的形式是[dummyNode(0, Node1), Node1(1, Node2), Node2(2, Node3), Node3(1, Node4), Node4(-3, Node5), Node5(10, Null)]，接下来开始初始化前缀和并遍历这个链表，初始化prefix = 0为前缀和。

　　我们可以得到：

　　dummyNode的前缀和为0 + 0，

　　Node1的前缀和为0 + 0 + 1 = 1，

　　Node2的前缀和为0 + 0 + 1 + 2 = 3，

　　Node3的前缀和为0 + 0 + 1 + 2 + 1 = 4，

　　Node4的前缀和为0 + 0 + 1 + 2 + 1 + (-3) = 1，

　　Node5的前缀和为0 + 0 + 1 + 2 + 1 + (-3) + 10 = 11，

　　在一一得到每个节点对应的前缀和后并将其加入到哈希表中Map<Integer, Node>，这里就会出现一个覆盖节点的操作，就是说当Node1节点存储到哈希表后，再存储Node4的时候，Node4会将Node1给覆盖掉，换句话说，遇到具有相同前缀和的节点，我们只存储最后的那一个，这也是为了我们第二步遍历时方便进行删除操作而设计的。那么最终我们的哈希表中就有了HashMap[(0, dummyNode), (1, Node4), (3, Node2), (4, Node3), (11, Node5)]。

　　我们为了进行删除操作需要进行二次遍历节点并统计前缀和，当第二次遍历时，如果哈希表中存在与当前遍历的节点具有相同的前缀和的节点，我们就进行删除操作。比如我们第二次遍历到了Node1，而哈希表中正好存在与Node1具有相同前缀和的Node4节点，那么直接将Node1的next指针指向Node4的下一个节点即可，至此就找到了一组总和为0的连续的节点序列，也就完成了删除，将Node1和Node5之间具有的和为0的连续节点序列给删除掉了。

　　以下是Java代码，仅供参考：

package algo;

import java.util.HashMap;
import java.util.Map;

public class removeZeroSumSublistsSolution_1171 {
    public ListNode removeZeroSumSublists(ListNode head){
        ListNode dummyNode = new ListNode(0);
        dummyNode.next = head;

        Map<Integer, ListNode> map = new HashMap<>(); // 构建一个哈希表，存储<prefix, Node>的键值对
        int prefix = 0; // 初始前缀和为0
        for(ListNode node = dummyNode; node != null; node = node.next){
            prefix += node.val; // 第一次统计前缀和
            map.put(prefix, node); // 覆盖操作
        }
        prefix = 0; // 重新初始化前缀和为0
        for(ListNode node = dummyNode; node != null; node = node.next){ 
            prefix += node.val; // 第二次统计前缀和
            node.next = map.get(prefix).next; // 删除操作
        }
        return dummyNode.next; // 返回head
    }
}