Medium

题目描述

给你一个链表的头节点 head，请你反复删除连续的、总和值为 0 的节点序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。你可以返回任何满足题目要求的答案。

（注意，下面示例中的所有序列，都是对 ListNode 对象序列化的表示。）

示例 1：

输入：head = [1,2,-3,3,1]
输出：[3,1]
解释：答案 [1,2,1] 也是正确的。

示例 2：

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

示例 3：

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

提示：

  • 给你的链表中将包含在 1 到 1000 个节点。
  • 每个节点的值都在 -1000 到 1000 之间。

解题思路

这道题的核心思想是利用前缀和的性质来删除和为0的连续子序列。

解题思路：

  1. 前缀和的关键性质：如果从位置i到位置j的连续子序列和为0，那么prefixSum[j] = prefixSum[i-1]，即两个位置的前缀和相等。

  2. 两次遍历法：

    • 第一次遍历：计算所有节点的前缀和，当遇到相同前缀和时，说明中间的节点构成和为0的序列。用哈希表记录每个前缀和对应的最后一个节点位置。
    • 第二次遍历：重新构建链表，跳过那些需要删除的节点段。

  3. 处理细节：

    • 添加虚拟头节点，方便处理边界情况
    • 前缀和为0意味着从链表开始到当前位置的所有节点都需要删除
    • 使用哈希表存储前缀和到节点的映射，相同前缀和的后出现节点会覆盖之前的记录

这种方法的巧妙之处在于，通过哈希表的覆盖特性，自然地处理了多个重叠的零和序列，最终保留的是每个前缀和对应的最后一个有效位置。

代码实现

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        unordered_map<int, ListNode*> prefixSumMap;
        int prefixSum = 0;
        
        // 第一次遍历：记录前缀和对应的节点
        for (ListNode* node = dummy; node; node = node->next) {
            prefixSum += node->val;
            prefixSumMap[prefixSum] = node;
        }
        
        // 第二次遍历：重建链表，跳过零和序列
        prefixSum = 0;
        for (ListNode* node = dummy; node; node = node->next) {
            prefixSum += node->val;
            node->next = prefixSumMap[prefixSum]->next;
        }
        
        return dummy->next;
    }
};

class Solution:
    def removeZeroSumSublists(self, head: Optional[ListNode]) -> Optional[ListNode]:
        dummy = ListNode(0)
        dummy.next = head
        
        prefix_sum_map = {}
        prefix_sum = 0
        
        # 第一次遍历：记录前缀和对应的节点
        node = dummy
        while node:
            prefix_sum += node.val
            prefix_sum_map[prefix_sum] = node
            node = node.next
        
        # 第二次遍历：重建链表，跳过零和序列
        prefix_sum = 0
        node = dummy
        while node:
            prefix_sum += node.val
            node.next = prefix_sum_map[prefix_sum].next
            node = node.next
        
        return dummy.next

public class Solution {
    public ListNode RemoveZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        Dictionary<int, ListNode> prefixSumMap = new Dictionary<int, ListNode>();
        int prefixSum = 0;
        
        // 第一次遍历：记录前缀和对应的节点
        for (ListNode node = dummy; node != null; node = node.next) {
            prefixSum += node.val;
            prefixSumMap[prefixSum] = node;
        }
        
        // 第二次遍历：重建链表，跳过零和序列
        prefixSum = 0;
        for (ListNode node = dummy; node != null; node = node.next) {
            prefixSum += node.val;
            node.next = prefixSumMap[prefixSum].next;
        }
        
        return dummy.next;
    }
}

var removeZeroSumSublists = function(head) {
    let dummy = new ListNode(0);
    dummy.next = head;
    
    let prefixSumMap = new Map();
    let prefixSum = 0;
    
    // 第一次遍历：记录前缀和对应的节点
    for (let node = dummy; node !== null; node = node.next) {
        prefixSum += node.val;
        prefixSumMap.set(prefixSum, node);
    }
    
    // 第二次遍历：重建链表，跳过零和序列
    prefixSum = 0;
    for (let node = dummy; node !== null; node = node.next) {
        prefixSum += node.val;
        node.next = prefixSumMap.get(prefixSum).next;
    }
    
    return dummy.next;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)需要遍历链表两次，每次O(n)
空间复杂度O(n)哈希表存储前缀和到节点的映射，最坏情况下存储n个键值对

相关题目