1171. 從鏈表中刪去總和值為零的連續(xù)結(jié)點(diǎn)
給你一個(gè)鏈表的頭結(jié)點(diǎn) head，請(qǐng)你編寫(xiě)代碼，反復(fù)刪去鏈表中由 總和 值為 0 的連續(xù)結(jié)點(diǎn)組成的序列，直到不存在這樣的序列為止。
刪除完畢后，請(qǐng)你返回最終結(jié)果鏈表的頭結(jié)點(diǎn)。

示例：

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

解題思路：
找到題目的關(guān)鍵點(diǎn)：和值為0的連續(xù)結(jié)點(diǎn)。我們來(lái)看看示例，如果我們選擇[-3, 3]這個(gè)區(qū)間，那么從左至右累加各個(gè)結(jié)點(diǎn)的值在這個(gè)區(qū)間前后是沒(méi)有變化的。也就是說(shuō)，用list來(lái)表示鏈表的累加和：[1, 3, 0, 3, 4]，可以看到Node(2)和Node(3)處的累加和是相等的。這就是解題的關(guān)鍵，找到累加和不變的區(qū)間，讓區(qū)間前一個(gè)Node的下一個(gè)Node等于區(qū)間結(jié)束后緊跟的下一個(gè)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

時(shí)間復(fù)雜度：O(N)，遍歷結(jié)點(diǎn)；
空間復(fù)雜度：O(N) ，存儲(chǔ)結(jié)點(diǎn)的累加和。

解法轉(zhuǎn)自 Java HashMap 兩次遍歷即可