1171. Remove Zero Sum Consecutive Nodes from Linked List

T: O(n)
S: O(n)

```java
/**
 * 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) {
        List<Integer> list = new ArrayList<>();
        ListNode dummy = new ListNode(0);
        dummy.next = head;

        Map<Integer, ListNode> map = new HashMap<>();
        map.put(0, dummy);

        int prefixSum = 0;
        ListNode i = dummy;
        while(i != null) {
            prefixSum += i.val;
            map.put(prefixSum, i);
            i = i.next;
        }

        prefixSum = 0;
        i = dummy;
        while(i != null) {
            prefixSum += i.val;
            i.next = map.get(prefixSum).next;
            i = i.next;
        }
        return dummy.next;
    }
}

/**

T: O(n)
S: O(n)

  1 2 -3 3 1 
0 1 3 0  3 4
  x x x       
     ans [3,1]     

  0 1 2 3
    x    x  
  1 2 3 -3 4
0 1 3 6  3 7  
      x  x
from start, find the same 

0 1 3->    3-> 7
    ->    ->  
    
 ans[1,2, 4] 

consecutive sequences -> subarray


  1 2 3 -3 -2
0 1 3 6  3  1



  -1,-2, 2,-1, 0
0 -1,-3,-1,-2,-2   

  1, -1
0 1  0


 [1,2,-2,2,-2,1,-1,1]
0 1 3  1 3  1 2 1  2

ans: [1,1]

so strick is...
build hashmap first
we have to look prefix hashmap again

https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/solutions/2079419/java-two-pass-solution-using-prefix-sum/?envType=daily-question&envId=2024-03-12

public static ListNode removeZeroSumSublists(ListNode head) {
    int prefixSum = 0;
    ListNode dummy = new ListNode(0);
    dummy.next = head;

    Map<Integer, ListNode> hashMap = new HashMap<>();
    hashMap.put(0, dummy);
    for (ListNode i = dummy; i != null; i = i.next) {
        prefixSum += i.val;
        hashMap.put(prefixSum, i);
    }
    prefixSum = 0;
    for (ListNode i = dummy; i != null; i = i.next) {
        prefixSum += i.val;
        i.next = hashMap.get(prefixSum).next;
    }
    return dummy.next;
}
 */
```