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

描述：

题解：

这道题很关键的地方就是如何判断连续相加等于0，有几种情况要考虑。题目给的示例中Test Case是残缺的，用它去解题会出错的，第一次提交就被坑了。

Case1:

[1,2,-3,3,1]

1+2-3 = 0
所以得到的是[3,1]

还有一种情况就是 -3+3 = 0
所以得到的是[1,2,1]

Case2:

[1,-1,2]
1-1 = 0
所以得到的是[2]

Case3:

[1,-1,1,-1]
1-1+1-1 = 0
所以得到的空

结合这几个Case和题目的示例能得到所有的情况了。

前面说关键点是判断连续相加为0，那么如何判断呢？这里通过累加的方法，遍历整个链表，把每个结点累加的和存到一个哈希表中。还有一个关键点也很重要，就是链表的头结点。

如果不用头结点，很容易出错。我们拿Case1来举例子。不用头结点的话

1->2->-3->3->1

初始化一个sum变量，值为0。我们先累加一下

sum: node
1: 1
3: 2
0: -3
3: 3
4: 1

可以看到，当结点为2的时候，sum为3，然后结点为3的时候，sum又为3，也就是说这两个结点之间的所有结点的和为0，所以我们得到的是[1,2,4]

这样看起来没什么问题，但是如果是[1,-1,1,-1]就出错了。我们分析一下：

sum: node
1: 1
0: -1
1: 1
0: -1

当结点为1的时候，sum为1，然后结点为下一个1的时候，sum又为1。那么得到的结果是[1,-1]，显然是错误。因为[1,-1]可以继续消掉。

我们加上头结点的话，再来分析一下这种情况。

head->1->-1->1->-1

sum: node
0: head
1: 1
0: -1
1: 1
0: -1

看，当结点为head的时候，sum为0，结点为-1的时候，sum又为0，所以得到的结果是head。因为head的初始值为0，如果结点相加等于0的话，后面总会有一个sum=0的结点，所以我们返回head.next就是我们想要的结果。

分析完毕后，我们遍历两次链表就可以得到结果了。第一次把sum和node存放到哈希表中，第二次根据累加的结果找到值相同的sum

ES6

export default function removeZeroSumSublists(head) {
  const dummy = new ListNode(null)
  dummy.next = head
  const map = new Map()
  let sum = 0
  //首次遍历，生成哈希表，key为当前节点总和，value为当前节点
  for (let p = dummy; p !== null; p = p.next) {
    sum += p.val
    map.set(sum, p)
  }

  //第二次遍历，如果当前节点处sum在下一处出现，表明两节点之间所有节点的和为0，直接删除区间所有节点
  sum = 0
  console.log(dummy)
  for (let q = dummy; q !== null; q = q.next) {
    sum += q.val
    q.next = map.get(sum).next
  }
  return dummy.next
}

时间复杂度：O(n)