手撕LeetCode #1171——Python

1171. 从链表中删去总和值为零的连续结点
给你一个链表的头结点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续结点组成的序列，直到不存在这样的序列为止。
删除完毕后，请你返回最终结果链表的头结点。

示例：

输入：head = [1,2,-3,3,1]
输出：[3,1]
提示：答案 [1,2,1] 也是正确的。

解题思路：
找到题目的关键点：和值为0的连续结点。我们来看看示例，如果我们选择[-3, 3]这个区间，那么从左至右累加各个结点的值在这个区间前后是没有变化的。也就是说，用list来表示链表的累加和：[1, 3, 0, 3, 4]，可以看到Node(2)和Node(3)处的累加和是相等的。这就是解题的关键，找到累加和不变的区间，让区间前一个Node的下一个Node等于区间结束后紧跟的下一个Node。

代码如下：

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        sumMap = {}
        node = dummy
        sum_node = 0
        while node:
            sum_node += node.val
            sumMap[sum_node] = node
            node = node.next
        
        sum_node = 0
        node = dummy
        while node:
            sum_node += node.val
            node.next = sumMap[sum_node].next
            node = node.next
        return dummy.next

时间复杂度：O(N)，遍历结点；
空间复杂度：O(N) ，存储结点的累加和。

解法转自 Java HashMap 两次遍历即可