又到了骗p币的时间
思路
prefix sum记录到目前的总和
hash map纪录每个prefix sum对应到node
当同个值出现两次，就把两个node中间的hash map删掉
并且把第一个node的next接到第二个node的next
记得一开始要在hash map里面放一个0
golang code:
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func removeZeroSumSublists(head *ListNode) *ListNode {
ans := &ListNode{0, head}
prefixSumToNode := make(map[int]*ListNode)
prefixSum := 0
temp := ans
for temp != nil {
prefixSum += temp.Val
if prev, found := prefixSumToNode[prefixSum]; found {
toRemove := prev.Next
p := prefixSum
for toRemove!=temp {
p+=toRemove.Val
delete(prefixSumToNode, p)
toRemove = toRemove.Next
}
prev.Next = temp.Next
} else {
prefixSumToNode[prefixSum] = temp
}
temp = temp.Next
}
return ans.Next
}