服装做外贸的网站建设,闲置tp路由自己做网站,校园网站建设方案策划书,湖南响应式网站建设哪家有文章目录 Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点问题描述#xff1a;分析代码 Remove Zero Sum Consecutive Nodes from Linked List 从链表中删去总和值为零的连续节点
问题描述#xff1a;
给你一个链表的头节点 head分析代码 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) {MapInteger,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) {MapInteger,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);pp.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
