Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences.
After doing so, return the head of the final linked list.  You may return any such answer.
 
(Note that in the examples below, all sequences are serializations of ListNode objects.)
Example 1:
Input: head = [1,2,-3,3,1]
Output: [3,1]
Note: The answer [1,2,1] would also be accepted.

Example 2:
Input: head = [1,2,3,-3,4]
Output: [1,2,4]

Example 3:
Input: head = [1,2,3,-3,-2]
Output: [1]

 
Constraints:

The given linked list will contain between 1 and 1000 nodes.
Each node in the linked list has -1000 <= node.val <= 1000.

Difficulty: interview

Starter code:

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
    self.val = val
    self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        

Solutions:
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        
        seen={}
        seen[0]=dummy=ListNode(0)
        dummy.next=head
        prev=0
        
        while head:
            prev+=head.val
            seen[prev]=head
            head=head.__next__
        head=dummy
        prev=0
        
        while head:
            prev+=head.val
            head.next=seen[prev].__next__
            head=head.__next__
        return dummy.__next__
        
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        prefix = 0
        seen_prefix = {}
        seen_prefix[0] = dummy = ListNode(0)
        dummy.next = head
        
        while head:
            prefix += head.val
            seen_prefix[prefix] = head
            head = head.next
            
        prefix = 0
        head = dummy
        
        while head:
            prefix += head.val
            head.next = seen_prefix[prefix].next
            head = head.next
            
        return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        prefix = 0
        seen = collections.OrderedDict()
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur.__next__
            cur = cur.__next__
        return dummy.__next__
                


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
#OrderedDict is used for ordered dictionaries
from collections import OrderedDict
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        nodes = OrderedDict()
        curr = head
        temp = ans = ListNode(0)
        prefix = 0
        nodes[prefix] = ListNode(0)
        while curr:
            prefix += curr.val
            node = None
            while prefix in nodes:
                node = nodes.popitem()
            if node:
                nodes[prefix] = node[1]
                curr = curr.__next__
                continue
                
            nodes[prefix] = curr
            curr = curr.__next__
        
        first = True
        for node in list(nodes.values()):
            if first:
                first = False
                continue
            temp.next = ListNode(node.val)
            temp = temp.__next__
        return ans.__next__
            

                
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prefixSum = 0 
        cur = head
        dic = {0:dummy}
        while cur:
            prefixSum += cur.val
            dic[prefixSum] = cur
            cur = cur.next
        head = dummy
        prefixSum = 0
        while head:
            prefixSum += head.val
            head.next = dic[prefixSum].next
            head = head.next
        return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:

    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dum = ListNode(next=head)
        sum_map = {0: dum}
        l = [0]
        
        while head:
            if head.val == 0:
                sum_map[l[-1]].next = head.__next__
                head = head.__next__
                continue
                
            sv = head.val + l[-1]
            
            if sv in sum_map:
                node = sum_map[sv]
                v = l.pop()
                while v != sv:
                    sum_map.pop(v, None)
                    v = l.pop()
                node.next = head.__next__
            else:
                sum_map[sv] = head
                
            l.append(sv)
            head = head.__next__
        return dum.__next__
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        prefix = 0
        seen = collections.OrderedDict()
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur = cur.__next__
        
        return dummy.__next__
            
    
            
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        node, prev, rsum = head, None, 0 # tbd = sublist To Be Deleted
        rsum_map = {}
        while node:
            rsum += node.val
            
            if rsum_map.get(rsum):
                link = rsum_map.get(rsum)
                link.next = node.__next__
                prev, node = link, node.__next__
                
                # update the map
                rsum_map = {}
                x, rsum = head, 0
                while x != node:
                    rsum+=x.val
                    rsum_map[rsum] = x
                    x = x.__next__
                continue
            
            rsum_map[rsum] = node
            if node.val == 0:
                if prev:
                    prev.next = node = node.__next__
                else:
                    head = node = node.__next__
                rsum_map.pop(0)
                continue
            elif rsum == 0:
                head = node = node.__next__
                prev = None
                rsum_map = {}
                continue
                  
            prev = node
            node = node.__next__
        return head


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        
        dummy = ListNode(0)
        hash = {0: dummy}
        dummy.next = head
        sum = 0
        i = head
        while i:
            sum+=i.val
            if sum in list(hash.keys()):
                tempsum = sum
                j = hash[sum].__next__
                while j != i:
                    tempsum+=j.val
                    del hash[tempsum]
                    j = j.__next__
                hash[sum].next = i.__next__
            else:
                hash[sum] = i
            i = i.__next__
        
        return dummy.__next__
        


from math import floor
from math import ceil
from math import sqrt
from collections import deque
import numpy
from _collections import deque
#from _ast import Num # LC doesn't like this
from heapq import *
from typing import List
import random

MOD = int(1e9 + 7)
BASE = 256
\"\"\"
Maintain a v to list mapping
this is the complete stale of final answer
two states to maintain
1. ansT


\"\"\"


# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        vToN = {}
        ps = 0
        vToN[0] = None

        curT = head
        ansH = None
        ansT = None

        while curT:
            newPs = ps + curT.val
            #print(newPs, vToN)

            if newPs in vToN:
                newAnsT = vToN[newPs]
                if newAnsT:

                    tempT = newAnsT
                    tempPs = newPs
                    while tempT != ansT:
                        tempT = tempT.next
                        tempPs += tempT.val
                        del vToN[tempPs]
                        
                    ansT = newAnsT
                    ansT.next = None
                else:
                    ansH = None
                    ansT = None
                    vToN.clear()
                    vToN[0] = None
            else:
                if ansT:
                    ansT.next = curT
                else:
                    ansH = curT
                ansT = curT
                vToN[newPs] = curT
            ps = newPs
            curT = curT.next
        
        
        return ansH


def toLL(l):
    head = ListNode(l[0])
    tail = head
    for i in range(1, len(l)):
        node = ListNode(l[i])
        tail.next = node
        tail = node
    return head

def pl(head):
    while head:
        print(head.val)
        head = head.next
\"\"\"
S = Solution()
head = [1,2,3,-3,-2]
head = [1,2,3,-3,3]
head = [1,2,3,-3,4]
head = [1,2,-3,3,1]
head = [1, -1]
pl(S.removeZeroSumSublists(toLL(head)))
#S.removeZeroSumSublists(None)
\"\"\"

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode()
        dummy.next = head
        m = {0: (dummy, 0)}
        cur_sum = cur = 0
        A = []
        def check(i, A):
            return all(not(s < i <= e)for s, e in A)
        while head:
            cur_sum += head.val
            cur += 1
            if cur_sum in m:
                i = m[cur_sum][1]
                if check(i, A):
                    m[cur_sum][0].next = head.next
                    A.append((i, cur))
                else:
                    m[cur_sum] = (head, cur)
            else:
                m[cur_sum] = (head, cur)
            head = head.next

        return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        p=head
        prev=None
        while(p):
            q=p.__next__
            s=p.val
            while(q and s):
                s+=q.val
                q=q.__next__
            if s==0:
                if p==head:
                    p=q
                    head=q
                else:
                    prev.next=q
                
                p=q
            else:
                prev=p
                p=p.__next__
            #print(prev.val,p.val if p else \" \")
        return head


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        prefix = 0
        seen = {}
        while cur:
            prefix += cur.val
            seen[prefix] = cur 
            cur = cur.__next__
        cur = dummy
        prefix = 0
        while cur:
            prefix += cur.val
            cur.next = seen[prefix].__next__
            cur = cur.__next__
        return dummy.__next__
            
    
            
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if(head is None):
            return None
        temp = head;
        array = self.createArray(temp);
        curSum = 0;
        index = 0;
        while(index < len(array)):
            for i in range(index, len(array)):
                curSum += array[i];
                if(curSum == 0):
                    self.clearOutArray(array, index, i);
                    index = i + 1;
                    curSum = 0;
            curSum = 0;
            index += 1;
        
        newNode = self.create(array);
        return newNode
   
    def clearOutArray(self, array, index, i):
        for i in range(index, i + 1):
            array[i] = None;
        return;
    
    def create(self, array):
        if(len(array) == 0):
            return None;
        node = None
        temp = None
        for i in range(0, len(array)):
            if(array[i] != None):
                if(node is None):
                    node = ListNode(array[i]);
                    temp = node;
                else:
                    node.next = ListNode(array[i]);
                    node = node.__next__;
        if(node is not None):
            node.next = None;
        return temp;
        
        
    def createArray(self, temp):
        array = [];
        while(temp != None):
            array.append(temp.val);
            temp = temp.__next__;
        return array;
    
    
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode(0)
        dummy.next = head
        prev = dummy
        temp = head
        while temp:
            s = 0
            start = temp
            while start:
                s += start.val
                if s == 0:
                    prev.next = start.__next__
                    break
                start = start.__next__
            if start == None:
                start = temp
                prev = temp
            temp = start.__next__
        return dummy.__next__
            
                    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if head is None: return head
        tot, cur = 0, head
        while cur:
            tot += cur.val
            cur = cur.__next__
            if tot == 0:
                return self.removeZeroSumSublists(cur)
        head.next = self.removeZeroSumSublists(head.next)
        return head
    
            
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        curr_sum = 0
        extra = ListNode(None)
        extra.next = head
        node = head
        prev = extra
        while node:
            tmp = node
            curr_sum = 0
            while tmp:
                curr_sum += tmp.val
                if curr_sum==0:
                    break
                else:
                    tmp = tmp.__next__
            # print (tmp.val, curr_sum)
            if curr_sum==0:
                if tmp:
                    prev.next = tmp.__next__
                else:
                    prev.next = None
                node = prev.__next__
            else:
                prev = node
                node = node.__next__
            
        return extra.__next__
            
   


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        # Create a dummy node to init the search
        pointer = ListNode(float(\"inf\"))
        # Point the dummy node to the head of the list
        pointer.next = head
        # create a reference to the given list and point the head to the dummy node
        curr = head
        head = pointer

        # Iterate over the node
        while head:
            # Store the current sum
            current_sum = 0

            # For each node compute the consecutive sum
            while curr:
                # Add the value of the node to the current sum
                current_sum += curr.val

                # If the consecutive sum is 0
                # Delete the reference to the
                # nodes that sum up to 0
                if current_sum == 0:
                    head.next = curr.next

                # Move to the next node
                curr = curr.next

            # Move the head
            head = head.next

            # Update the current node
            # to be the next element 
            # of the head. This resets
            # the \"state\" as in the start
            if head:
                curr = head.next

        # Return the next element of the 
        # dummy pointer, which is going
        # to be the updated head of the list
        return pointer.next            

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode(float('inf'))
        dummy.next = head
        cur = head
        head = dummy
        
        while head:
            r_sum = 0
            
            while cur:
                r_sum += cur.val
                if r_sum == 0:
                    head.next = cur.__next__
                
                cur = cur.__next__
            head = head.__next__
            if head:
                cur = head.__next__
        
        return dummy.__next__
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if not head:
            return None
        node = temp = ListNode(0)
        node.next = head
        
        while temp:
            total = 0
            second = temp.next
            while second:
                total += second.val
                if total == 0:
                    temp.next = second.next
                second = second.next
            temp = temp.next
            
        return node.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode()
        dummy.next = head
        curr = head
        prefix_sum = [0]
        d = {}
        d[0] = dummy
        i = 1
        
        
        while curr:
            prefix_sum.append(prefix_sum[-1] + curr.val)
            d[i] = curr
            i += 1
            curr = curr.__next__
        
        i = 0
        while i < len(prefix_sum):
            j = len(prefix_sum) - 1
            while i <= j:
                if prefix_sum[j] - prefix_sum[i] == 0:
                    d[i].next = d[j].__next__
                    i = j + 1
                j -= 1
        
        return dummy.__next__


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        Head = ListNode(0)
        Head.next = head
        cur = Head;
        while(cur != None):        
            sum=0
            while(head!=None):
                sum = sum + head.val
                if(sum==0):                
                    cur.next = head.__next__
                head  = head.__next__
            
            cur=cur.__next__
            if(cur!=None):            
                head = cur.__next__
            
        
        return Head.__next__     


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        nodeList = []
        temp = head
        while temp:
            nodeList.append(temp.val)
            temp = temp.next
        
        x = 0
        while x < len(nodeList):
            y = x
            sum = 0
            while y < len(nodeList):
                sum = sum + nodeList[y]
                if sum == 0:
                    # delete array index x to y
                    del nodeList[x:y+1]
                    x -= 1
                    break
                y += 1
            x += 1
        print(nodeList)

        newHead = ListNode()
        currhead = newHead
        for node in nodeList:
            currhead.next = ListNode(node)
            currhead = currhead.next

        return newHead.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        prefix = 0
        seen = collections.OrderedDict()
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur = cur.__next__
        return dummy.__next__
    
            
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if(head is None):
            return None
        temp = head;
        array = self.createArray(temp);
        curSum = 0;
        index = 0;
        while(index < len(array)):
            for i in range(index, len(array)):
                curSum += array[i];
                if(curSum == 0):
                    self.clearOutArray(array, index, i);
                    index = i + 1;
                    curSum = 0;
            curSum = 0;
            index += 1;
        
        return self.create(array);
   
    def clearOutArray(self, array, index, i):
        for i in range(index, i + 1):
            array[i] = None;
        return;
    
    def create(self, array):
        if(len(array) == 0):
            return None;
        node = None
        temp = None
        for i in range(0, len(array)):
            if(array[i] != None):
                if(node is None):
                    node = ListNode(array[i]);
                    temp = node;
                else:
                    node.next = ListNode(array[i]);
                    node = node.__next__;
        if(node is not None):
            node.next = None;
        return temp;
        
    def createArray(self, temp):
        array = [];
        while(temp != None):
            array.append(temp.val);
            temp = temp.__next__;
        return array;
    
    
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        a=[]
        temp = head
        while(temp):
            a.append(temp.val)
            temp = temp.next
        # print(a)
        l = len(a)
        i = l-1
        x=0 
        ind = []
        while(i>=1):
            e = a[i]
            j = i-1
            while(j>=0):
                e+=a[j]
                if e==0:
                    ind.append((j,i))
                    i = j
                    break
                j-=1
            i-=1
        # print(ind)
        li = len(ind)
        j =0
        while(j<li):
            s,e = ind[j][0],ind[j][1]
            for i in range(e,s-1,-1):
                # print(a,i)
                a.pop(i)
                
            j+=1
        h = ListNode(0)
        temp = h
        while a:
            e = a.pop(0)
            if e !=0:
                temp.next =ListNode(e)
                temp =temp.next
        return h.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        l = []
        result = head
        while head != None:
            num = head.val
            bFlag = False
            if num == 0:
                bFlag = True
                if result == head:
                    result = head.next
                else:
                    l[len(l) - 1].next = head.next
            else:
                for i in range(len(l) - 1, -1, -1):
                    num += l[i].val
                    if num == 0:
                        bFlag = True
                        if i == 0:
                            result = head.next
                        else:
                            l[i - 1].next = head.next
                        for j in range(len(l) - 1, i - 1, -1):
                            l.pop()
                        break
            if bFlag == False:
                l.append(head)
            head = head.next
        return result

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if(head is None):
            return None
        temp = head;
        array = self.createArray(temp);
        
        curSum = 0;
        index = 0;
        while(index < len(array)):
            for i in range(index, len(array)):
                curSum += array[i];
                if(curSum == 0):
                    self.clearOutArray(array, index, i);
                    index = i + 1;
                    curSum = 0;
            curSum = 0;
            index += 1;
        
        finalArray = [];
        for num in array:
            if(num  != None):
                finalArray.append(num);
        
        newNode = self.create(finalArray);
        return newNode
                    
    def clearOutArray(self, array, index, i):
        for i in range(index, i + 1):
            array[i] = None;
        return;
    
    def create(self, array):
        if(len(array) == 0):
            return None;
        else:
            node = ListNode(array[0]);
            temp = node;
            for i in range(1, len(array)):
                node.next = ListNode(array[i]);
                node = node.__next__;
            node.next = None;
        return temp;
        
        
    def createArray(self, temp):
        array = [];
        while(temp != None):
            array.append(temp.val);
            temp = temp.__next__;
        return array;
    
    
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if(head is None):
            return None
        temp = head;
        array = self.createArray(temp);
        
        curSum = 0;
        index = 0;
        while(index < len(array)):
            for i in range(index, len(array)):
                curSum += array[i];
                if(curSum == 0):
                    self.clearOutArray(array, index, i);
                    index = i + 1;
                    curSum = 0;
            curSum = 0;
            index += 1;
        
        newNode = self.create(array);
        return newNode
                    
    def clearOutArray(self, array, index, i):
        for i in range(index, i + 1):
            array[i] = None;
        return;
    
    def create(self, array):
        if(len(array) == 0):
            return None;
        else:
            node = None
            temp = None
            for i in range(0, len(array)):
                if(array[i] != None):
                    if(node is None):
                        node = ListNode(array[i]);
                        temp = node;
                    else:
                        node.next = ListNode(array[i]);
                        node = node.__next__;
            if(node is not None):
                node.next = None;
        return temp;
        
        
    def createArray(self, temp):
        array = [];
        while(temp != None):
            array.append(temp.val);
            temp = temp.__next__;
        return array;
    
    
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if head == None:
            return None
        def check(node):
            if node == None:
                return None
            n = check(node.__next__)
            node.next = n
            t = node
            c = 0
            while t != None:
                c += t.val
                if c == 0:
                    return t.__next__
                t = t.__next__
            return node
                
            
                
        res = check(head)
        return res
                    


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        arr = []
        while head:
            arr.append(head.val)
            head = head.__next__
        D = [0]*(len(arr)+1)
        for i in range(1,len(D)):
            D[i] = D[i-1] + arr[i-1]
        
        tmp_dict = {}
        for i in range(len(D)):
            if D[i] not in tmp_dict:
                tmp_dict[D[i]] = [i]
            else:
                tmp_dict[D[i]].append(i)
        i = 0
        remove = []
        while i<len(D):
            if len(tmp_dict[D[i]])>1:
                if i!=tmp_dict[D[i]][-1]:
                    remove.append([i,tmp_dict[D[i]][-1]])
                i = tmp_dict[D[i]][-1] + 1
            else:
                i += 1
        
        remove_idx = []
        for i in range(len(remove)):
            remove_idx += [e for e in range(remove[i][0],remove[i][1])]
        
        res = []
        for i in range(len(arr)):
            if i not in remove_idx:
                res.append(arr[i])
        
        if len(res)==0:
            return None
        else:
            head = ListNode(res[0])
            pre = head
            for i in range(1,len(res)):
                node = ListNode(res[i])
                pre.next = node
                pre = node
            return head
                


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        p = head
        nums = []
        while p:
            nums.append(p.val)
            p = p.__next__
        
        def check(nums):
            cur, k = 0, 0
            stack = []
            acc = [0] + list(accumulate(nums))
            for i, n in enumerate(nums):
                for j in range(k, i + 1):
                    if acc[i + 1] - acc[j] == 0:
                        stack.append((j, i))
                        k = i + 1
            return stack
        
        stack = check(nums)
        while stack:
            while stack:
                j, i = stack.pop()
                nums[j: i + 1] = []
            stack = check(nums)
        
        if not nums:
            return None
        ans = ListNode(nums[0])
        p = ans
        for i in range(1, len(nums)):
            p.next = ListNode(nums[i])
            p = p.__next__
        return ans
            
            
            
            
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
from collections import deque

class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        s = []
        cur = head
        
        while cur != None:
            if cur.val == 0:
                cur = cur.__next__
                continue
            
            back_sum = 0
            end_i = -1
            for i in range(len(s))[::-1]:
                back_sum += s[i].val
                
                if cur.val + back_sum == 0:
                    end_i = i
                    
            if end_i != -1:
                for j in range(len(s) - 1, end_i - 1, -1):
                    s.pop()
            else:
                s.append(cur)
            
            cur = cur.__next__
            
        for i in range(len(s)):
            if i < len(s) - 1:
                s[i].next = s[i+1]
            else:
                s[i].next = None
               
        if len(s) > 0:
            return s[0]
        else:
            return None


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        prefix = 0 
        seen = collections.OrderedDict()
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur = cur.__next__ 
        return dummy.__next__
            
    
            
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def deleteNodes(self, node: ListNode, num: int) -> ListNode:
        assert node != None
        assert num > 0
        dummy = ListNode(0, node)
        prev = dummy
        while node != None and num != 0:
            prev.next = node.next
            node = node.next
            num = num - 1
        assert num == 0
        return dummy.next
    
    def findSumZero(self, head: ListNode) -> int:
        assert head != None
        n = 1
        s = 0
        node = head
        while node != None:
            s = s + node.val
            if s == 0:
                return n 
            node = node.next
            n = n + 1
        return 0
        
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        dummy = ListNode(0, head)
        prev = dummy
        node = head
        while node != None:
            n = self.findSumZero(node)
            if n > 0:
                node_next = node
                for i in range(n):
                    node_next = node_next.next
                prev.next = node_next
                node = node_next
            else:
                prev = node
                node = node.next
        return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        
        array = []
        modified = False
        node = head
        #print(\"Head: \", head)
        while node:
            #print(\"node: \", node.val, modified, matched)
            next_node = node.__next__
            matched = False
            if node.val == 0:
                matched = True
                modified = True
                if len(array) > 0:
                    array[-1].next = next_node
                else:
                    head = next_node
            
            else:
                tsum = 0
                #print(\"For: \", node.val)
                for i in range(len(array) -1, -1, -1):
                    tsum += array[i].val
                    if tsum + node.val == 0:
                        matched = True
                        modified = True
                        #print(i)
                        if i != 0:
                            j = 0
                            popi = len(array) - i
                            while j != popi:
                                array.pop()
                                j += 1
                            array[i-1].next = next_node
                            #print(array[i-1].val, next_node.val, head)
                        else:
                            # all elements removed
                            head = next_node
                            array = []
                    # elif tsum + node.val > 0:
                    #     break
                        
            if not matched:
                array.append(node)
            node = next_node
        #print(\"op head: \", head)
        if modified:
            return self.removeZeroSumSublists(head)
        else:
            return head        
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        curr = head
        while curr is not None and curr.val == 0:
            curr = curr.__next__
            
        dummy = ListNode(0, curr)
        if curr is not None:  
            memo = [[dummy],[curr, curr.val]]
        curr = curr.__next__ if curr is not None else None
        while curr is not None:
            last_index = len(memo) - 1
            if curr.val == 0:
                # print(\"here\")
                memo[last_index][0].next = curr.__next__
                curr = curr.__next__
                continue
            curr_list = [curr]
            flag = True
            for i in range(1, len(memo[last_index])):
                val = memo[last_index][i] + curr.val
                # print(val)
                if val == 0:
                    # print(f'last: {memo[last_index][0].val}, curr: {curr.val}')
                    memo[i - 1][0].next = curr.__next__
                    memo = memo[:i]
                    # print(memo)
                    flag = False
                    break
                else:
                    curr_list.append(val)
            if flag:
                curr_list.append(curr.val)
                memo.append(curr_list)
            curr = curr.__next__
        return dummy.__next__
                


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        if(head is None):
            return head;
        prev = None;
        currentNode = head;
        nextNode = head;
        newHead = head;
        curSum = 0;
        while(currentNode != None):
            while(nextNode != None):
                curSum += nextNode.val
                if(curSum == 0):
                    if(prev is None):
                        currentNode = nextNode.__next__;
                        newHead = currentNode
                        nextNode = nextNode.__next__;
                    else:
                        prev.next = nextNode.__next__
                        currentNode = nextNode.__next__;
                        nextNode = nextNode.__next__;
                else:
                    nextNode = nextNode.__next__;
            curSum = 0;
            if(currentNode is None):
                break
            prev = currentNode;
            currentNode = currentNode.__next__;
            nextNode = currentNode;
        return newHead
        
            


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        def removeZeros(arr):
            for i in range(len(arr)):
                tsum = 0
                for j in range(i, len(arr)):
                    tsum += arr[j]
                    if tsum == 0:
                        return True, [i, j]
            
            return False, [len(arr), len(arr)-1]
        
        arr = []
        current = head
        while current is not None:
            arr.append(current.val)
            current = current.__next__
        
        ret = removeZeros(arr)
        flag = ret[0]
        while flag:
            start = ret[1][0]
            end = ret[1][1]
            arr = arr[:start] + arr[end+1:]
            ret = removeZeros(arr)
            flag = ret[0]
        
        head = None
        current = head
        for n in arr:
            if current is None:
                current = ListNode(n)
                head = current
            else:
                current.next = ListNode(n)
                current = current.__next__
            
        return head
        
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:        
        root = ListNode(next=head)
        r, h = root, head
        
        while h:
            # node.val == 0
            if not h.val:
                r.next = h.__next__
                h = h.__next__
            else:
                p, q = root, root.__next__
                while q != h:
                    q.val += h.val
                    
                    # find a zero-sum sequence
                    if not q.val:
                        p.next = h.__next__
                        break
                        
                    p, q = q, q.__next__
                if q == h:
                    r, h = h, h.__next__
                else:
                    r, h = p, h.__next__

        # revert to nodes' original values
        p, q = root, root.__next__
        while q:
            p.val -= q.val
            p, q = q, q.__next__
        
        return root.__next__


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        # Try starting from every possible starting point basically
        while True:
            n = head
            size = 0
            while n != None:
                size += 1
                n = n.__next__
            i = 0
            flag = False
            while i < size:
                node = head
                k=0
                prev = head
                while k < i:
                    prev = node
                    if node == None:
                        break
                    node = node.__next__
                    k += 1
                i += 1
                curr_sum = 0
                n = prev
                d = {}
                while node != None:
                    curr_sum += node.val
                    if curr_sum == 0:
                        if i == 1:
                            head = node.__next__
                        else:
                            n.next = node.__next__
                        flag = True
                        break
                    node = node.__next__
                    
            if not flag:
                break
        
        return head


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        # Try starting from every possible starting point basically
        while True:
            n = head
            size = 0
            while n != None:
                size += 1
                n = n.__next__
            i = 0
            flag = False
            while i < size:
                node = head
                k=0
                prev = head
                while k < i:
                    prev = node
                    if node == None:
                        break
                    node = node.__next__
                    k += 1
                i += 1
                curr_sum = 0
                n = prev
                while node != None:
                    curr_sum += node.val
                    if curr_sum == 0:
                        if i == 1:
                            head = node.__next__
                        else:
                            n.next = node.__next__
                        flag = True
                        break
                    node = node.__next__
                    
            if not flag:
                break
        
        return head


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, H: ListNode) -> ListNode:
        A, b = ListNode(0), 1; A.next = H
        while b:
            s, b, D, C = 0, 0, {0:A}, A.next
            while C != None:
                s += C.val
                if s in D:
                    D[s].next, b = C.next, 1
                    break
                else: D[s], C = C, C.next
        return A.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        cur = dummy = ListNode(0)
        dummy.next = head
        prefix = 0
        seen = collections.OrderedDict()
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur = cur.next
        return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
#OrderedDict is used for ordered dictionaries
from collections import OrderedDict
class Solution:
    def removeZeroSumSublists(self, head):
        cur = dummy = ListNode(0)
        dummy.next = head
        prefix = 0
        seen = collections.OrderedDict()
        while cur:
            prefix += cur.val
            node = seen.get(prefix, cur)
            while prefix in seen:
                seen.popitem()
            seen[prefix] = node
            node.next = cur = cur.__next__
        return dummy.__next__
            

                
        


# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def remove_range(self, head, start_prev, stop):
        if start_prev is None:
            return stop
        else:
            start_prev.next = stop
            return head
    
    def detect_zero(self, head):
        prev = None
        stop = head
        hist = {0: None}
        acc = 0
        while stop is not None:
            acc += stop.val
            try:
                start_prev = hist[acc]
            except KeyError:
                hist[acc] = stop
                prev = stop
                stop = stop.__next__
                continue
            return True, start_prev, stop.__next__
        return False, None, None
    
    def removeZeroSumSublists(self, head: ListNode) -> ListNode:
        while True:
            found, start_prev, stop = self.detect_zero(head)
            if not found:
                return head
            head = self.remove_range(head, start_prev, stop)