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

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 哈希表（推荐）
相似题目

题目描述

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

思路分析

解法一：前缀和 + 哈希表（推荐）

核心思路：

引入虚拟头结点，方便处理从头开始被删除的区间。

第一遍遍历计算前缀和，并记录“某个前缀和最后出现的节点”。

第二遍再遍历一次，若当前前缀和在后面出现过，则中间区间和为 0，直接跳过。

复杂度分析：

时间复杂度：O(n)，其中 n 表示链表长度。

空间复杂度：O(n)，其中哈希表存储前缀和对应的节点。

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        Map<Integer, ListNode> last = new HashMap<>();

        int sum = 0;
        for (ListNode cur = dummy; cur != null; cur = cur.next) {
            sum += cur.val;
            // 记录该前缀和最后出现的位置
            last.put(sum, cur);
        }

        sum = 0;
        for (ListNode cur = dummy; cur != null; cur = cur.next) {
            sum += cur.val;
            // 跳过前缀和相同的区间
            cur.next = last.get(sum).next;
        }

        return dummy.next;
    }
}

func removeZeroSumSublists(head *ListNode) *ListNode {
    dummy := &ListNode{Val: 0, Next: head}

    last := make(map[int]*ListNode)

    sum := 0
    for cur := dummy; cur != nil; cur = cur.Next {
        sum += cur.Val
        // 记录该前缀和最后出现的位置
        last[sum] = cur
    }

    sum = 0
    for cur := dummy; cur != nil; cur = cur.Next {
        sum += cur.Val
        // 跳过前缀和相同的区间
        cur.Next = last[sum].Next
    }

    return dummy.Next
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和、哈希表
325. 和等于 k 的最长子数组长度	中等	前缀和、哈希表
523. 连续的子数组和	中等	前缀和、同余
974. 和可被 K 整除的子数组	中等	前缀和、哈希表
203. 移除链表元素	简单	链表删除

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/47592196