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

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

难度:

标签:

题目描述

代码结果

运行时间: 48 ms, 内存: 15.4 MB


/*
  In this approach, we use a combination of Java Stream to iterate and filter elements.
  However, since LinkedList manipulation can't fully be achieved with Stream alone, 
  we will still use basic loops to manage nodes. The Stream will primarily help in handling
  collections and sequences.
*/

import java.util.HashMap;
import java.util.stream.Stream;

class ListNode {
    int val;
    ListNode next;
    ListNode(int x) { val = x; }
}

public class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        HashMap<Integer, ListNode> prefixMap = new HashMap<>();
        int prefixSum = 0;
        prefixMap.put(0, dummy);

        Stream.iterate(dummy, node -> node.next != null, node -> node.next).forEach(node -> {
            prefixSum += node.val;
            if (prefixMap.containsKey(prefixSum)) {
                ListNode start = prefixMap.get(prefixSum).next;
                int sum = prefixSum + start.val;
                while (sum != prefixSum) {
                    prefixMap.remove(sum);
                    start = start.next;
                    sum += start.val;
                }
                prefixMap.get(prefixSum).next = start.next;
            } else {
                prefixMap.put(prefixSum, node);
            }
        });
        return dummy.next;
    }
}

解释

方法:

此题解采用前缀和和哈希表的方法来解决问题。首先,创建一个虚拟头节点 dummy,该节点的下一个节点是给定链表的头节点 head。使用一个字典 pre_sum 来存储到当前节点为止的前缀和以及对应的最后一个节点。遍历链表两次,第一次遍历计算每个节点的前缀和,并在 pre_sum 中存储该前缀和最后一次出现的节点。第二次遍历使用前缀和来直接跳过总和为零的子链表,通过将当前节点的 next 指针指向 pre_sum 中存储的前缀和对应的节点的 next。这样,所有总和为零的子链表都被删除了。

时间复杂度:

O(n)

空间复杂度:

O(n)

代码细节讲解

🦆
在算法中使用前缀和和哈希表的原理是什么?这种方法如何确保可以找到并删除所有总和为零的子链表?
在此算法中,前缀和是用来记录从链表开始到当前节点的所有值的累加和。哈希表(在此用作前缀和到节点的映射)用于快速查找是否之前出现过相同的前缀和。如果在链表的某个位置出现了与之前某个位置相同的前缀和,这意味着这两个位置之间的节点总和为零。通过将前一个位置的节点直接连接到当前位置的下一个节点,可以有效地删除总和为零的子链表。这种方法通过映射前缀和到其最后出现的节点,确保了即使有多个相同的前缀和出现,也能通过最后一次出现的位置来删除中间总和为零的部分,从而确保找到并删除所有总和为零的子链表。
🦆
为什么在第一次遍历链表时需要更新前缀和对应的最后一个节点,而不是第一个遇到的节点?
在第一次遍历时,维护前缀和对应的最后一个节点是因为我们希望在发现总和为零的子链表时,能够直接跳过这整个子链表。如果我们记录的是第一个遇到的节点,那么当再次遇到相同的前缀和时,我们只能确认从第一个记录的节点到当前节点的子链表总和为零,但这无法帮助我们处理后续可能还有的总和为零的子链表。通过更新为最后一个节点,我们确保了每次遇到相同的前缀和时,都能跳过从上次记录的节点到当前节点之间的全部节点,这样更有效地处理了所有可能的情况。
🦆
给出的题解中提到了使用虚拟头节点 `dummy`,它的具体作用是什么?在没有虚拟头节点的情况下,这个算法是否还能正确执行?
虚拟头节点 `dummy` 主要用于简化链表操作,特别是在头部节点需要被删除或修改时。通过添加一个虚拟头节点,我们保证了即使原始链表的头节点需要被删除(例如头部的前几个节点构成的子链表总和为零),我们也能轻松地处理这一情况,因为我们总是可以通过 `dummy.next` 来访问更新后的真实头节点。如果没有虚拟头节点,算法仍然可以执行,但需要额外的条件判断来处理头节点的特殊情况,这会使得算法的实现更加复杂和容易出错。

相关问题