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

记住「前缀和相等 ⇒ 中间段为 0」。本动画演示的就是代码的两遍法:先建哈希(记最后出现),再跳指针。

准备 · 虚拟头 + 前缀和 0：在表头前想象一个「虚拟头」,它的前缀和是 0,先记进哈希 {0: dummy}。第一遍:从第 0 个节点开始累加,记每个前缀和「最后出现」的节点。

第一遍 · #0 前缀和 1：走到 #0(值 1),前缀和累加到 1。把「1 → #0」记进哈希。

第一遍 · #1 前缀和 4：走到 #1(值 3),前缀和累加到 4。把「4 → #1」记进哈希。

第一遍 · #2 前缀和 6：走到 #2(值 2),前缀和累加到 6。把「6 → #2」记进哈希。

第一遍 · #3 前缀和 3：走到 #3(值 -3),前缀和累加到 3。把「3 → #3」记进哈希。

第一遍 · #4 前缀和 1：走到 #4(值 -2),前缀和累加到 1。把「1 → #4」记进哈希(前缀和 1 之前出现过,这里用 #4 覆盖旧的,两遍法只保留每个前缀和「最后出现」的节点)。

第一遍 · #5 前缀和 6：走到 #5(值 5),前缀和累加到 6。把「6 → #5」记进哈希(前缀和 6 之前出现过,这里用 #5 覆盖旧的,两遍法只保留每个前缀和「最后出现」的节点)。

第一遍 · #6 前缀和 11：走到 #6(值 5),前缀和累加到 11。把「11 → #6」记进哈希。

第一遍 · #7 前缀和 6：走到 #7(值 -5),前缀和累加到 6。把「6 → #7」记进哈希(前缀和 6 之前出现过,这里用 #7 覆盖旧的,两遍法只保留每个前缀和「最后出现」的节点)。

第一遍完成 · 哈希定稿：第一遍走完,哈希里每个前缀和都指向它「最后一次」出现的节点。注意前缀和 1 → #4、前缀和 6 → #7(都被后面的覆盖成最后位置)。第二遍就靠它一步跳过零和段。

开始第二遍 · 跳指针：哈希已建好。第二遍再从虚拟头走一遍:在每个节点处,用「当前前缀和最后出现处的下一个」直接接上,一步跳过零和段。

第二遍 · 虚拟头：cur 从虚拟头出发,前缀和 0。查哈希 {0:dummy},dummy.next 仍是第 0 个,不变。cur 前进到第 0 个节点。

第二遍 · #0 算前缀和：cur 走到 #0,前缀和累加到 1。接下来查哈希:前缀和 1 最后出现在哪个节点。

第二遍 · 查哈希 1 → #4：查哈希:前缀和 1 最后出现在 #4。#0 和 #4 前缀和相同,说明 #0 之后到 #4 这一段(#1、#2、#3、#4)总和为 0,下一步一步跳过。

第二遍 · #0.next 跳到 #5：让 #0.next = #4.next = #5,中间 #1、#2、#3、#4 整段被跳过(删除,打删除线)。cur 前进到 #5。

第二遍 · #5 算前缀和：cur 走到 #5,前缀和累加到 6。接下来查哈希:前缀和 6 最后出现在哪个节点。

第二遍 · 查哈希 6 → #7：查哈希:前缀和 6 最后出现在 #7。#5 和 #7 前缀和相同,说明 #5 之后到 #7 这一段(#6、#7)总和为 0,下一步一步跳过。

第二遍 · #5.next 跳到 null：让 #5.next = #7.next = null,中间 #6、#7 整段被跳过(删除,打删除线)。cur 前进到 链表末尾,第二遍结束。

第二遍结束：第二遍走完,所有总和为 0 的段都被指针一步步跳过删掉(打删除线):#1、#2、#3、#4、#6、#7。

完成：剩下绿色的 [1, 5] 就是答案。整条流程:第一遍建「前缀和→最后节点」哈希,第二遍跳指针一次清掉所有零和段。

边界先想清:全删、单 0、无可删。

面试重点:讲清两遍法「记最后出现 + 跳指针」与虚拟头的作用。