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

约 5 分钟
文章信息 9 个分类 2 个标签
分类
LeetCode CodeTop 中等 未解决 5-10 字节 阿里 华为 快手
标签
哈希表 链表

题目描述

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

image-20260928235251269

image-20260928235251270

题意分析

反复删除链表中总和为零的一段连续节点，直到剩余链表再也没有这样的片段，返回剩余链表的头节点。可以返回任意一个符合要求的结果，不要求保留最多节点。

删除可能发生在开头、中间或末尾，整条链表也可能被删空。每次逐段尝试再重新扫描会重复计算，可以利用前缀和识别零和区间，并一次跳过当前节点后面能形成的最长零和片段。

解法：前缀和映射到最后节点

核心思路

[!blue]

一个节点对应的前缀和，是从链表开头累加到它的节点值总和。如果节点 a 与后面的节点 b 前缀和相同，那么从 a.next 到 b 的总和就是两者之差，也就是零。删除这段时保留 a，把 a.next 直接连到 b.next 即可。

在真实头节点前放一个值为零的虚拟头 dummy，让它也参与前缀计算。它表示还没经过任何真实节点时的零前缀，因此从真实头开始的零和段也能按同样的连接规则删除，无需单独修改头节点。

第一遍保持链表不变，记录“前缀和 → 最后出现该前缀和的节点”。遇到相同前缀时持续覆盖，保留最靠后的节点。第二遍再从 dummy 开始重新累加，对当前前缀找到最后节点，执行 node.next = last[prefix].next，跳过两者之间全部零和节点。

删除一段和为零的节点，不会改变后面保留节点的累计和，因此第二遍沿修改后的链表计算出的前缀，仍与第一遍原链表中的前缀一致，旧映射可以继续使用。若末次节点就是当前节点，连接保持原样；否则一定连向它之后的位置，不会倒退形成环。

为什么一次向后扫描就够？处理当前前缀后，同值前缀的所有后续出现都已被跳过，因为使用的是最后一次出现的位置。后续删除又只跳过零和片段，不改变保留节点的前缀值。因此最终留下的各前缀互不相同，而没有相同前缀就不再存在零和连续片段。

解题步骤

  1. 创建值为零且指向原头节点的 dummy，初始化空映射与前缀和 0。
  2. 第一遍从 dummy 遍历原链表，累加当前节点值，并覆盖保存当前前缀对应的节点。
  3. 将前缀和重新设为 0，第二遍再次从 dummy 出发。
  4. 累加当前值后，把当前后继连到同前缀最后节点的后继，再沿新的连接前进。
  5. 遍历结束后返回 dummy.next，它可能为空。

代码实现

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)$，保存前缀映射。

关键点总结

[!green]

  • 相同前缀之间才是零和段：删除的是当前节点之后到末次节点为止的部分，当前节点本身保留。
  • 先完整记录，再修改连接：第一遍建立全局末次位置，第二遍利用它直接跳过零和段。
  • 零和删除保持后续前缀：这是修改链表后仍能复用原映射的依据。
  • 沿新连接继续：已经被跳过的节点不需要再处理，最后剩余链表中不会有重复前缀。

易错点总结

[!yellow]

  • 保存第一次出现的位置：本方案需要向后跳到最后一次出现之后，改成首次位置可能连回前面的节点并形成环。
  • 连接到末次节点本身：零和段包含这个节点，应连接到它的后继，否则删不完整，甚至可能自环。
  • 第二遍没有清零前缀：两遍的累计起点必须一致，否则映射不再对应当前前缀。
  • 遗漏虚拟头的零前缀：会使从真实头开始的零和片段无法按统一规则删除。

相似题目

题目 难度 关联与区别
560. 和为 K 的子数组 中等 重复前缀和表示中间段和为0，本题进一步通过节点映射跳过对应链段。
325. 和等于 k 的最长子数组长度 中等 原题按前缀位置求最长区间，本题记录同前缀的后续节点以删除零和部分，所需位置策略不同。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/47592196
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！