leetcode1171. 从链表中删去总和值为零的连续节点

**从链表中删去总和值为零的连续节点**

###问题描述给定一个单链表，删除所有总和值为零的连续节点。请注意，这些相邻节点的值之和等于零。

示例1:

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

输出：[3,1,-3,2,1]

解释：从链表中删去总和为零的连续节点（-3、3）、(1,-3) 和 (2, -3)。

示例2:

输入：head = [0,1,2]

输出：[0,1,2]

解释：没有需要删除的连续节点，因此链表保持不变。

### 解决方案我们将使用一个哈希表来存储每个节点的值和下一个节点的值。然后，我们可以遍历链表，检查是否有连续的节点，其值之和为零。如果有，我们就删掉这些连续的节点。

####代码实现

class ListNode:
 def __init__(self, x):
 self.val = x self.next = Nonedef removeZeroSumSublists(head: ListNode) -> ListNode:
 dummy = ListNode(0)
 dummy.next = head prefix_sum = {0: dummy}
 cur_sum =0 prev = dummy while head:
 cur_sum += head.val if cur_sum not in prefix_sum:
 prefix_sum[cur_sum] = head else:
 # Found a zero-sum sublist, remove it start = prefix_sum[cur_sum].next end = head prev.next = head.next while start != end:
 start_val = start.val start = start.next end_val = end.val end = end.next # Update the next pointer of the node before the start of the sublist prev.next = start # Move the previous pointer to the node after the end of the sublist prev = end head = head.next head = head.next return dummy.next# Example usage:
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(-3)
head.next.next.next = ListNode(3)
head.next.next.next.next = ListNode(1)

new_head = removeZeroSumSublists(head)

while new_head:
 print(new_head.val, end=" ")
 new_head = new_head.next

###说明* 我们首先创建一个虚拟头结点（dummy），并将原链表的头结点指向它。
* 然后，我们使用哈希表 `prefix_sum` 来存储每个节点的值和下一个节点的值。我们也维护一个当前和 `cur_sum`，用于计算从虚拟头结点到当前节点的前缀和。
* 当我们遍历链表时，如果当前和不在哈希表中，我们就更新哈希表并继续向后移动。
* 如果当前和已经存在于哈希表中，这意味着我们找到了一个总和为零的连续子列表。我们将其从链表中删除，并更新指针以跳过该子列表。
* 最终，返回虚拟头结点的下一个节点作为新链表的头结点。

### 时间复杂度时间复杂度为 O(n)，其中 n 是链表中的节点数。我们只遍历链表一次，并且每个操作（哈希表查找、更新和删除）都是常数时间复杂度。

### 空间复杂度空间复杂度为 O(n)。我们使用一个哈希表来存储前缀和，这需要额外的空间。