leetcode链表之从链表中删除总和值为零的连续结点

1171、从链表中删除总和值为零的连续结点

题目：

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

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

你可以返回任何满足题目要求的答案。

示例1：

输入：head = [1,2,-3,3,1]
输出：[3,1]

示例2：

输入：head = [1,2,3,-3,4]
输出：[1,2,4]

示例3：

输入：head = [1,2,3,-3,-2]
输出：[1]

思路：

连续结点为0，那么当累加和的时候，如果累加和出现和前面一样的值时，说明这两个累加和一致中间的这些数总值为0，这样就很自然的想到，用hash来记录之前的累计和对应的结点。

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if not head: return head
        sumNode = {}
        sum = 0
        cur = vhead = ListNode(0, head)
        # 这里用stack来进行删除，避免由于删除结点，导致hash中的累加和存在导致的问题
        stack = []
        while cur:
            sum += cur.val
            if sum in sumNode:
                # 如果发现相同的累加和，删除sumNode中缓存的值，并及时更新stack数组
                prevIndex = stack.index(sum)
                for prevSum in stack[prevIndex+1:]:
                    sumNode.pop(prevSum, "None")
                stack = stack[0:prevIndex+1]
                sumNode[sum].next = cur.next
            else:
                sumNode[sum] = cur
                stack.append(sum)
            cur = cur.next
        return vhead.next