【算法】Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点

Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点

问题描述：

给你一个链表的头节点 head，请你编写代码，反复删去链表中由 总和 值为 0 的连续节点组成的序列，直到不存在这样的序列为止。

删除完毕后，请你返回最终结果链表的头节点。

节点数量 范围[1,1000]，节点值范围[-1000,1000]

分析

这个问题要求把链表中和为0的连续节点删除，很明显是一个前缀和处理，而且数据规模不大，暴力处理也可以。
首先使用一个dummy，方便处理，使用map记录每个节点的前缀和，map[前缀和,节点].
在遍历链表的过程中，首先计算该节点的前缀和sum，如果sum之前出现过，说明遇到了一段需要删除的区间，删除处理。此时map需要清空，然后从头，再进行遍历循环，直到遍历到结尾。
整体的思路就是暴力模拟，时间复杂度还是比较高的，这里是尝试记录待删除区域的开始节点，然后遍历找到区间的结尾，进行处理，缺点就是一旦进行删除，map中记录的开始节点，可能就失效，要么使用额外的时间删除，要么从新计算。

另一种思路也是记录，但是这里是记录前缀和最后出现的节点。这样第一次遍历时完成map记录。
第二次遍历，一旦发现出现了前缀和，就可以找到这个区域，进行删除。因为删除的区间和是0，所以不影响前缀和记录，同样也不会影响map中记录的前缀和节点。

代码

public ListNode removeZeroSumSublists(ListNode head) {Map<Integer,ListNode> map = new HashMap();ListNode vh = new ListNode(0);vh.next = head;ListNode p = vh,pre =null;int sum = 0; while(p!=null){sum += p.val;if(map.containsKey(sum)){pre = map.get(sum);pre.next = p.next;map.clear();p = vh;sum =0;}else{map.put(sum,p);p = p.next;}}return vh.next; }

时间复杂度 O(N?)

空间复杂度： O(N)

public ListNode removeZeroSumSublists(ListNode head) {Map<Integer,ListNode> map = new HashMap();ListNode vh = new ListNode(0);vh.next = head;ListNode p = head;int sum = 0;while(p!=null){sum += p.val;map.put(sum,p);p=p.next;}p = vh;sum = 0;while(p!=null){sum += p.val;if(map.containsKey(sum)){ListNode q = map.get(sum);p.next = q.next; }p = p.next;} return vh.next; }

时间复杂度 O(N)

空间复杂度： O(N)

Tag

Hash linkedlist