给你一个链表的头节点 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 <= node.val <= 1000.
建立哈希表,key为节点值的前缀和,value为节点。
第一次循环遍历,累加前缀和,并逐一写入哈希表,重复的值会自动替换为最新的。
第二次遍历,让节点指向存在哈希表中当前前缀和的节点,中间跳过的部分总和即为 。
/**
* Definition for singly-linked list.
* 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 dummy= new ListNode(0);
dummy.next=head;
Map<Integer,ListNode>seen=new HashMap<>();
int prefix=0;
for(ListNode node=dummy;node!=null;node=node.next){
prefix+=node.val;
seen.put(prefix,node);
}
prefix=0;
for(ListNode node=dummy;node!=null;node=node.next){
prefix+=node.val;
node.next=seen.get(prefix).next;
}
return dummy.next;
}
}
标签:node,ListNode,val,1171,值为,next,链表,节点
From: https://blog.51cto.com/u_15983387/6458696