Remove Zero Sum Consecutive Nodes from Linked List
给一个列表, remove里面所有的和为0的subarray. 这题很奇葩, 要求remove所有的. 所以要设个loop, 每次都检查是不是remove了. 如果remove了, 下次再来一次, 直到没有remove, loop=false,就停止. 我这个做法, 慢的一批…. 用map来检查subarray是不是有和为0的情况. 注意map(0,-1) 是为了防止[0]和[1,-1]这种情况
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode removeZeroSumSublists(ListNode head) { List<Integer> l = new ArrayList<>(); while(head != null){ l.add(head.val); head = head.next; } ListNode nhead = new ListNode(0); ListNode p = nhead; Map<Integer, Integer> map = new HashMap<>(); int sum = 0; map.put(0, -1); boolean loop = false; for(int i = 0; i < l.size(); i++) { sum += l.get(i); if(map.get(sum) != null) { int n = map.get(sum) + 1; for(int j = n; j <= i; j++) { l.remove(n); } loop = true; break; } map.put(sum, i); } for(int i = 0; i < l.size(); i++) { p.next = new ListNode(l.get(i)); p = p.next; } if (loop) return removeZeroSumSublists(nhead.next); else return nhead.next; } } |