题目描述

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

分析

若链表节点的两个前缀和相等，说明两个前缀和之间的连续节点序列的和为 0，那么可以消去这部分连续节点。

我们第一次遍历链表，用哈希表 last记录前缀和以及对应的链表节点，对于同一前缀和s，后面出现的节点覆盖前面的节点。

接下来，我们再次遍历链表，若当前节点 cur 的前缀和 s在 last出现，说明 cur与 last[s]之间的所有节点和为 0，我们直接修改 cur 的指向，即 cur.next=last[s].next，这样就删去了这部分和为 000 的连续节点。继续往后遍历，删除所有和为 0的连续节点。

最后返回链表的头节点 dummy.next。

代码

class Solution {

  public ListNode removeZeroSumSublists(ListNode head) {

    ListNode dummy = new ListNode(0, head);

    Map<Integer, ListNode> last = new HashMap<>();

    int s = 0;

    ListNode cur = dummy;

    while(cur!=null){

      s+=cur.val;

      last.put(s, cur);

      cur = cur.next;

    }

    s=0;

    cur=dummy;

    while(cur!=null){

      s+=cur.val;

      cur.next = last.get(s).next;

      cur = cur.next;

    }

    return dummy.next;

  }

}