Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点

问题描述：

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

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

节点数量 范围[1,1000]，节点值范围[-1000,1000]

分析

这个问题要求把链表中和为0的连续节点删除，很明显是一个前缀和处理，而且数据规模不大，暴力处理也可以。
首先使用一个dummy，方便处理，使用map记录每个节点的前缀和，map[前缀和,节点].
在遍历链表的过程中，首先计算该节点的前缀和sum，如果sum之前出现过，说明遇到了一段需要删除的区间，删除处理。此时map需要清空，然后从头，再进行遍历循环，直到遍历到结尾。
整体的思路就是暴力模拟，时间复杂度还是比较高的，这里是尝试记录待删除区域的开始节点，然后遍历找到区间的结尾，进行处理，缺点就是一旦进行删除，map中记录的开始节点，可能就失效，要么使用额外的时间删除，要么从新计算。

另一种思路也是记录，但是这里是记录前缀和最后出现的节点。这样第一次遍历时完成map记录。
第二次遍历，一旦发现出现了前缀和，就可以找到这个区域，进行删除。因为删除的区间和是0，所以不影响前缀和记录，同样也不会影响map中记录的前缀和节点。

代码

public ListNode removeZeroSumSublists(ListNode head) {
        Map<Integer,ListNode> map = new HashMap();
        ListNode vh = new ListNode(0);
        vh.next = head;
        ListNode p = vh,pre =null;
        int sum = 0; 
        while(p!=null){
            sum += p.val;
            if(map.containsKey(sum)){
                pre = map.get(sum);
                pre.next = p.next;
                map.clear();
                p = vh;
                sum =0;
            }
            else{
                map.put(sum,p);
                p = p.next;
            }
        }
        return vh.next; 
    }

时间复杂度 O(N?)

空间复杂度： O(N)

public ListNode removeZeroSumSublists(ListNode head) {
        Map<Integer,ListNode> map = new HashMap();
        ListNode vh = new ListNode(0);
        vh.next = head;
        ListNode p = head;
        int sum = 0;
        while(p!=null){
            sum += p.val;
            map.put(sum,p);
            p=p.next;
        }
        p = vh;
        sum = 0;
        while(p!=null){
            sum += p.val;
            if(map.containsKey(sum)){
                ListNode q = map.get(sum);
                p.next = q.next; 
            }
            p = p.next;
        } 
        return vh.next; 
    }

时间复杂度 O(N)

空间复杂度： O(N)

Tag

Hash linkedlist