作者:
JIWP (JIWP)
2024-03-12 23:28:38又到了騙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
}