1171. 从链表中删去总和值为零的连续节点：链表的前缀和数组.md

题目简述：

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

题目链接：1171. 从链表中删去总和值为零的连续节点

一遍主扫描链表前缀和（偏直白）

这一思路是我自己想到的。我一看到问题描述就立刻想到了 binary indexed tree，仔细一想本问题只需要固定的前缀和数组，并不需要动态查询与更新，所以直接用哈希表构建链表的前缀和数组即可。

思路

计算前缀和数组就好了，同时对前缀和数组做值域统计以快速找出相同前缀和的位置（由于是链表问题，因此做前缀和到节点的映射，考虑虚拟头节点 dummy）。如果某段子链表的总和值为 0，我们不必去更新前缀和数组，因此这段子链表对前缀和没有贡献，计算后续前缀和时不受此影响——只是需要将该段子链表内每个节点对应的前缀和从值域统计中移除，表示该段整体不再考虑。

我们用一个例子进行说明：

1. 假如前缀和数组 prefix 为 [-1, 1, 2, 3, 1, 4]

2. 那么相应地原数组 vals 为 [-1, 2, 1, 1, -2, 3]

3. 发现前缀和数组中存在两个重复值 prefix[1] 与 prefix[4]，于是有 prefix[4] -prefix[1] = 0

4. prefix[4] -prefix[1] = 0 对应到原数组上意味着 vals[2] + vals[3] + vals[4] = 0，我们可以回到原数组中观察，发现确实如此，有 1 + 1 + (-2) = 0

5. 所以我们移除 vals[2]、vals[3] 与 vals[4] 即可

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        long sum = 0;
        ListNode dummy = new ListNode(0, head);
        ListNode node = head;

        Map<Long, ListNode> map = new HashMap<>();
        map.put(0L, dummy);

        while (node != null) {
            sum += node.val;
            ListNode start = map.putIfAbsent(sum, node);
            if (start != null) {
                // 从值域统计中移除即将要被删除节点对应的前缀和
                ListNode tmpNode = start.next;
                long tmpSum = sum;
                while (tmpNode != node) {
                    tmpSum += tmpNode.val;
                    map.remove(tmpSum);
                    tmpNode = tmpNode.next;
                }
                start.next = node.next;
            }
            node = node.next;
        }

        return dummy.next;
    }
}

两遍扫描的链表前缀和（偏技巧）

思路

本问题还有另一种解法，这是我后来学习到的。时间与空间复杂度上与上文的方法没有数量级上的差异。

同样考虑链表前缀和，进行两次扫描，但在第一次遍历时直接考虑 map.put(sum, node)。相对的，在上一种方法中我们使用的是 map.putIfAbsent(sum, node)，发现有重复前缀和时立即删除刚刚发现的和为零的子链表。在这里我们不这样做，第一次遍历的含义是记录最后出现的前缀和为 sum 的节点。

接着进行第二次扫描，重新计算累加前缀和 sum，这次扫描不再遍历链表的所有节点，而是当我们在一个节点 node 上时，尝试直接跳转到 map.get(sum)，如果成功则删除上一个节点至 map.get(sum) 内的所有元素——在有 GC 的语言中，对链表进行该操作等价于操纵一个指针。当然，如果全局都只有该节点的前缀和为 sum 那么这会导致原地踏步，所以我们做一个节点的相等判断就好了，如果相等则转移至 node.next，否则再转移至 map.get(sum)。

这很巧妙，因为这样做能够保证每次删除都尽量删除了最多的元素，从而不影响后续结果，因此不需要再去更新前缀和的值域统计——因为后面的元素不会再用到这部分节点的前缀和，要么前缀和的值被映射到更后面未被删除的节点，要么后面未被删除的节点中不存在等于该值的前缀和，这两种情况都不需要我们去更新值域统计，代码会更简洁。

代码

算法的时间复杂度为 $O(n)$，空间复杂度为 $O(n)$。

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        long sum = 0;
        ListNode dummy = new ListNode(0, head);
        ListNode node = dummy;

        Map<Long, ListNode> map = new HashMap<>();

        while (node != null) {
            sum += node.val;
            map.put(sum, node);
            node = node.next;
        }

        sum = 0;
        node = dummy;
        while (node != null) {
            sum += node.val;
            ListNode next_ = map.get(sum);
            if (node == next_) {
                node = node.next;
                continue;
            }
            node.next = next_.next;
            node = node.next;
        }

        return dummy.next;
    }
}