1171. Remove Zero Sum Consecutive Nodes from Linked List #
题目 #
-
给定链表头节点
head，反复删去链表中由 总和 值为0的连续节点组成的序列，直到不存在这样的序列为止。 -
删除完毕后，返回最终结果链表的头节点。
思路 #
- 考察第
k个链表结点，判断其是否位于某个 零子序列 中，只需通过检查第k-1个结点的前缀和在>=k结点处是否再次出现。 - 可以通过两次遍历链表，借助
HashMap实现这一需求- 第一趟遍历，计算每个结点的前缀和，并构建前缀和与最远结点的映射关系
- 第二趟遍历，从哨兵结点开始，从映射中查找当前前缀和对应的结点，若找到则移除之间的结点。
代码 #
public class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
class Solution {
public ListNode removeZeroSumSublists(ListNode head) {
ListNode sentinel = new ListNode(0, head);
Map<Integer, ListNode> map = new HashMap<>();
map.put(0, sentinel);
int sum = 0;
for (ListNode ptr = head; ptr != null; ptr = ptr.next) {
sum += ptr.val;
map.put(sum, ptr);
}
sum = 0;
for (ListNode ptr = sentinel; ptr != null; ptr = ptr.next) {
sum += ptr.val;
if (map.containsKey(sum) == true) ptr.next = map.get(sum).next);
}
return sentinel.next;
}
}