从链表中删去总和值为零的连续节点
难度:
标签:
题目描述
代码结果
运行时间: 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`,它的具体作用是什么?在没有虚拟头节点的情况下,这个算法是否还能正确执行?
▷