package leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
 */
public class Problem1171 {
    public static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }

        @Override
        public String toString() {
            return "" + val;
        }
    }

    public ListNode removeZeroSumSublists(ListNode head) {
        List<ListNode> nodes = new ArrayList<>();
        for (ListNode n = head; n != null; n = n.next) {
            nodes.add(n);
        }
        int sum = 0;
        while (true) {
            Map</*sum*/ Integer, /*index*/ Integer> map = new HashMap<>();
            int startIdx = 0;
            int endIdx = 0;
            sum = 0;
            boolean removed =  false;
            for (int i = 0; i < nodes.size(); i++) {
                sum += nodes.get(i).val;
                if (map.containsKey(sum)) {
                    startIdx = map.get(sum) + 1;
                    endIdx = i;
                    removed = true;
                    break;
                } else {
                    map.put(sum, i);
                }
            }
            if (!removed) {
                break;
            }
            List<ListNode> tmp = new ArrayList<>();
            for (int i = 0; i < nodes.size(); i++) {
                if (i < startIdx || i > endIdx) {
                    tmp.add(nodes.get(i));
                }
            }
            nodes = tmp;
        }
        if (sum == 0) {
            return null;
        }
        ListNode answer = null;
        for (int i = 0; i < nodes.size(); i++) {
            if (nodes.get(i).val == 0) {
                continue;
            }
            if (answer == null) {
                answer = nodes.get(i);
            } else {
                nodes.get(i - 1).next = nodes.get(i);
            }
            nodes.get(i).next = null;
        }
        return answer;
    }

    private static void print(ListNode head) {
        System.out.print("[ ");
        for (ListNode n = head; n != null; n = n.next) {
            System.out.print(n.val + " ");
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        Problem1171 prob = new Problem1171();

        ListNode head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(-3);
//        head.next.next.next = new ListNode(3);
//        head.next.next.next.next = new ListNode(1);
//        print(prob.removeZeroSumSublists(head)); // [3,1]
//
//        head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(-3);
//        head.next.next.next.next = new ListNode(4);
//        print(prob.removeZeroSumSublists(head)); // [1,2,4]
//
//        head = new ListNode(1);
//        head.next = new ListNode(2);
//        head.next.next = new ListNode(3);
//        head.next.next.next = new ListNode(-3);
//        head.next.next.next.next = new ListNode(-2);
//        print(prob.removeZeroSumSublists(head)); // [1]
//
//        head = new ListNode(3);
//        head.next = new ListNode(4);
//        head.next.next = new ListNode(5);
//        head.next.next.next = new ListNode(-2);
//        head.next.next.next.next = new ListNode(-3);
//        head.next.next.next.next.next = new ListNode(2);
//        head.next.next.next.next.next.next = new ListNode(6);
//        print(prob.removeZeroSumSublists(head)); // [3, 2]
//
//        head = new ListNode(1);
//        head.next = new ListNode(-1);
//        print(prob.removeZeroSumSublists(head)); // []
//
//        head = new ListNode(0);
//        head.next = new ListNode(2);
//        print(prob.removeZeroSumSublists(head)); // [2]

        head = new ListNode(-1);
        head.next = new ListNode(1);
        head.next.next = new ListNode(-2);
        head.next.next.next = new ListNode(-1);
        print(prob.removeZeroSumSublists(head)); // [-2, -1]
    }
}

@@ -368,101 +368,8 @@
    %7D
-%0A%0A        @Override%0A        public String toString() %7B%0A            return %22%22 + val;%0A        %7D
 %0A   
@@ -1084,32 +1084,195 @@
          break;%0A
+                %7D if (sum == 0) %7B%0A                    startIdx = 0;%0A                    endIdx = i;%0A                    removed = true;%0A                    break;%0A
                 
@@ -1683,67 +1683,8 @@
   %7D%0A
-        if (sum == 0) %7B%0A            return null;%0A        %7D%0A
     
@@ -1764,89 +1764,8 @@
 ) %7B%0A
-            if (nodes.get(i).val == 0) %7B%0A                continue;%0A            %7D%0A
     
@@ -2181,32 +2181,32 @@
 %22 %22);%0A        %7D%0A
+
         System.o
@@ -2231,1863 +2231,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1171 prob = new Problem1171();%0A%0A        ListNode head = new ListNode(1);%0A//        head.next = new ListNode(2);%0A//        head.next.next = new ListNode(-3);%0A//        head.next.next.next = new ListNode(3);%0A//        head.next.next.next.next = new ListNode(1);%0A//        print(prob.removeZeroSumSublists(head)); // %5B3,1%5D%0A//%0A//        head = new ListNode(1);%0A//        head.next = new ListNode(2);%0A//        head.next.next = new ListNode(3);%0A//        head.next.next.next = new ListNode(-3);%0A//        head.next.next.next.next = new ListNode(4);%0A//        print(prob.removeZeroSumSublists(head)); // %5B1,2,4%5D%0A//%0A//        head = new ListNode(1);%0A//        head.next = new ListNode(2);%0A//        head.next.next = new ListNode(3);%0A//        head.next.next.next = new ListNode(-3);%0A//        head.next.next.next.next = new ListNode(-2);%0A//        print(prob.removeZeroSumSublists(head)); // %5B1%5D%0A//%0A//        head = new ListNode(3);%0A//        head.next = new ListNode(4);%0A//        head.next.next = new ListNode(5);%0A//        head.next.next.next = new ListNode(-2);%0A//        head.next.next.next.next = new ListNode(-3);%0A//        head.next.next.next.next.next = new ListNode(2);%0A//        head.next.next.next.next.next.next = new ListNode(6);%0A//        print(prob.removeZeroSumSublists(head)); // %5B3, 2%5D%0A//%0A//        head = new ListNode(1);%0A//        head.next = new ListNode(-1);%0A//        print(prob.removeZeroSumSublists(head)); // %5B%5D%0A//%0A//        head = new ListNode(0);%0A//        head.next = new ListNode(2);%0A//        print(prob.removeZeroSumSublists(head)); // %5B2%5D%0A%0A        head = new ListNode(-1);%0A        head.next = new ListNode(1);%0A        head.next.next = new ListNode(-2);%0A        head.next.next.next = new ListNode(-1);%0A        print(prob.removeZeroSumSublists(head)); // %5B-2, -1%5D%0A    %7D
 %0A%7D%0A

Solve problem 1171