## Description

Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.

After doing so, return the head of the final linked list. You may return any such answer.

(Note that in the examples below, all sequences are serializations of ListNode objects.)

Example 1:

Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.


Example 2:

Input: head = [1,2,3,-3,4]
Output: [1,2,4]


Example 3:

Input: head = [1,2,3,-3,-2]
Output: 


Constraints:

• The given linked list will contain between 1 and 1000 nodes.
• Each node in the linked list has -1000 <= node.val <= 1000.

## Solutions

### 1. 前缀和-Hash Table

# Time: O(n)
# Space: O(n)
class ListNode:
def __init__(self, x):
self.val = x
self.next = None

class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
dummy = ListNode(0)
sum_hash = collections.defaultdict()
sum_hash = dummy
while node:
sum_hash.clear()
node = dummy
sum_hash = dummy
else:
node = node.next
return dummy.next

# 105/105 cases passed (52 ms)
# Your runtime beats 24.11 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.3 MB)


不从最开始的位置遍历：

# Time: O(n)
# Space: O(n)
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
cur = dummy = ListNode(0)
prefix = 0
seen = collections.OrderedDict()
while cur:
prefix += cur.val
node = seen.get(prefix, cur)
while prefix in seen:
seen.popitem()
seen[prefix] = node
node.next = cur = cur.next
return dummy.next

# 105/105 cases passed (48 ms)
# Your runtime beats 28.44 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.3 MB)


### 2. Two Passes

第一遍遍历计算从开始节点开始当当前节点的所有结点的和，有相同也只会更新最近的那个位置，这个位置在第二遍遍历的时候就能直接当做隔空对接的位置！

# Time: O(n)
# Space: O(n)
class Solution:
def removeZeroSumSublists(self, head: ListNode) -> ListNode:
cur = dummy = ListNode(0)
prefix = 0
sum_hash = collections.defaultdict()
while cur:
prefix += cur.val
sum_hash[prefix] = cur
cur = cur.next

cur = dummy
prefix = 0
while cur:
prefix += cur.val
cur.next = sum_hash[prefix].next
cur = cur.next
return dummy.next

# 105/105 cases passed (40 ms)
# Your runtime beats 82.67 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (13.2 MB)