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

LC每日一题，参考1171. 从链表中删去总和值为零的连续节点 - 力扣（Leetcode）。

题目

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

删除完毕后，请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。
（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

输入：head = [1,2,3,-3,4]
输出：[1,2,4]
输入：head = [1,2,3,-3,-2]
输出：[1]

解题思路

• 前缀和+哈希表：连续序列值为零,即前缀和某个区间为零,即某两个前缀和相等,可使用哈希表查找。

前缀和+哈希表

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        //前缀和+哈希 (和为零即当前前缀和是否已经存在)
        int[] presum = new int[1001];
        int i = 0;
        HashMap<Integer,ListNode> map = new HashMap<>();
        ListNode dummy = new ListNode(0,head);
        map.put(0,dummy);
        while(head != null) {
            presum[i+1] = presum[i] + head.val;
            ListNode node = map.get(presum[i+1]);
            if(node != null) {//删除节点区间(node,head]以及哈希
                int j = i;
                while(j >= 0 && presum[j] != presum[i+1]){
                    map.remove(presum[j--]);//map.put(presum[j--],null);
                }
                node.next = head.next;
            }else{//存储
                map.put(presum[i+1],head);
            }
            head = head.next;
            i++;
        }
        //[1,2,3,-3,-2] -> 0 1 3 6 3 1
        return dummy.next;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为链表长度,遍历链表一次n,删除区间最多不超过n次。
• 空间复杂度：O(n)，前缀和数组n,哈希表空间不超过n。