LeetCode 1171. 从链表中删去总和值为零的连续节点
目录
题目描述
题意分析
给一条单链表，反复删除其中「相加等于 0 的连续片段」，直到链表里再也找不出这样的片段为止，返回剩下的链表头。不同删除顺序可能得到不同结果，题目允许返回任意一个合法答案。
最容易被忽略的是「反复」两个字。删掉一段之后，原本被它隔开的左右两截会直接拼在一起，拼接处可能又凑出一段新的零和片段。所以既不能扫一遍就收工，也不能只删掉遇到的第一段短的了事——这道题的难点从来不是「找出一段和为 0」，而是「一次性把连锁反应全部处理干净」。
约束透露的信号有三条。节点数不超过 1000、节点值在 -1000 到 1000 之间，说明累加值最大只有 $10^6$ 量级，
int完全够用，不必担心溢出。值可正可负，意味着片段和沿链表方向既不单调也不非负，任何依赖「和随右端点增大而增大」的收缩技巧在这里都不成立。而「删除会引发新的删除」这个性质，本质上是在暗示：要找一个能把「某段和为 0」变成 $O(1)$ 可判定的等价条件，而不是一轮一轮地重扫。边界有三种。删除可能从头节点就开始，比如
[1,-1,2]要返回[2]；整条链表可能被删空，比如[1,2,-3]要返回空；同一段区域里可能嵌套着好几段零和片段，必须一起消失，而不是只消掉最内层的那一段。
解法：前缀和映射到最后节点
核心思路
在链表前加入值为 0 的虚拟头节点，并从它开始计算前缀和。若节点
a与后续节点b的前缀和相同，则a.next到b的元素和为 0，这一整段都应删除。第一遍遍历用哈希表记录“前缀和 → 最后一次出现该前缀和的节点”。选择最后一次，是为了在第二遍遇到同一前缀和时，一次跳过尽可能长的零和区间，也能覆盖嵌套和连续的零和段。
第二遍重新计算前缀和。到达节点
node时，将node.next指向last[prefix].next。被跳过区间的总和为 0，所以删除后后续保留节点的前缀和不变，哈希表仍可继续使用。虚拟头节点让“从原头节点开始的一段和为 0”也能用同一逻辑删除，无需单独处理头指针。
解题步骤
- 创建值为 0、指向
head的虚拟头节点。- 第一遍从虚拟头开始累加前缀和，持续覆盖哈希表中的同名键，使其保存最后一个对应节点。
- 第二遍再次从虚拟头累加前缀和。
- 对每个节点执行
node.next = last.get(prefix).next，跳过当前节点之后的零和区间。- 返回
dummy.next。例如
[1,2,-3,3,1]的前缀和依次为0,1,3,0,3,4。前缀和 0 的最后位置在-3，因此虚拟头直接连到后面的3，结果为[3,1]。
代码实现
import java.util.HashMap;
import java.util.Map;
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode dummy = new ListNode(0, head);
Map<Integer, ListNode> last = new HashMap<>();
int prefix = 0;
for (ListNode node = dummy; node != null; node = node.next) {
prefix += node.val;
last.put(prefix, node);
}
prefix = 0;
for (ListNode node = dummy; node != null; node = node.next) {
prefix += node.val;
node.next = last.get(prefix).next;
}
return dummy.next;
}
}
func removeZeroSumSublists(head *ListNode) *ListNode {
dummy := &ListNode{Val: 0, Next: head}
last := make(map[int]*ListNode)
prefix := 0
for node := dummy; node != nil; node = node.Next {
prefix += node.Val
last[prefix] = node
}
prefix = 0
for node := dummy; node != nil; node = node.Next {
prefix += node.Val
node.Next = last[prefix].Next
}
return dummy.Next
}
复杂度分析
- 时间复杂度：$O(n)$。两次线性遍历中，每个节点只被访问常数次。
- 空间复杂度：$O(n)$。哈希表最多保存每个前缀和对应的一个节点。
关键点总结
- 两个位置前缀和相等，说明它们之间的连续区间和为 0。
- 映射保存最后一次出现位置，才能一次删除最远的零和段。
- 第二遍通过改写
next指针完成删除，不需要逐节点寻找区间。- 虚拟头统一处理从链表头开始被删除的情况。
易错点总结
- 哈希表保存第一次出现位置，会留下本应一并删除的嵌套区间。
- 第一遍发现重复前缀和时不能立即改链，否则会改变后续遍历路径，导致映射不完整。
- 第二遍应连接到
last.get(prefix).next，若连接到节点本身会形成环。- 不使用虚拟头时，删除以原头节点开头的零和段需要额外分支。
- 只做一轮局部删除容易漏掉删除后新形成的零和连续段。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 560. 和为 K 的子数组 | 中等 | 数组版原型，统计个数所以哈希表存的是「累加值出现次数」 |
| 525. 连续数组 | 中等 | 把 0 视作 -1，转成本题的「和为 0」，但记录首次出现以求最长 |
| 523. 连续的子数组和 | 中等 | 判定条件从「累加值相等」放宽为「对 k 取模相等」，还有长度至少 2 |
| 325. 和等于 k 的最长子数组长度 | 中等 | 求最长所以必须记首次出现，与本题记最后一次恰好相反 |
| 724. 寻找数组的中心下标 | 简单 | 只需比较左右两侧累加值，连哈希表都不用 |
| 437. 路径总和 III | 中等 | 累加值搬到树的根到当前节点路径上，回溯时要撤销哈希表计数 |
| 203. 移除链表元素 | 简单 | 同样靠 dummy 处理头节点被删，但删除条件是单节点值而非区间和 |
| 82. 删除排序链表中的重复元素 II | 中等 | 也是整段删除 + dummy，判定靠相邻值相等而非查表 |
| 19. 删除链表的倒数第 N 个结点 | 中等 | dummy 的经典用途，定位改用快慢指针相隔 n 步 |