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: MEDIUM
Tags: Data structures
Skill types: Data structures

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:
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__


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


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__


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__


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


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__


class Solution:

	def removeZeroSumSublists(self, head: ListNode) -> ListNode:
		(node, prev, rsum) = (head, None, 0)
		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__)
				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


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__


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


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__
		return head


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__


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


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__


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


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__
			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__


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__


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


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__


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__


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:
					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


class Solution:

	def removeZeroSumSublists(self, head: ListNode) -> ListNode:
		a = []
		temp = head
		while temp:
			a.append(temp.val)
			temp = temp.next
		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
		li = len(ind)
		j = 0
		while j < li:
			(s, e) = (ind[j][0], ind[j][1])
			for i in range(e, s - 1, -1):
				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


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


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


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


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


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


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


class Solution:

	def removeZeroSumSublists(self, head: ListNode) -> ListNode:
		array = []
		modified = False
		node = head
		while node:
			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
				for i in range(len(array) - 1, -1, -1):
					tsum += array[i].val
					if tsum + node.val == 0:
						matched = True
						modified = True
						if i != 0:
							j = 0
							popi = len(array) - i
							while j != popi:
								array.pop()
								j += 1
							array[i - 1].next = next_node
						else:
							head = next_node
							array = []
			if not matched:
				array.append(node)
			node = next_node
		if modified:
			return self.removeZeroSumSublists(head)
		else:
			return head


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:
				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
				if val == 0:
					memo[i - 1][0].next = curr.__next__
					memo = memo[:i]
					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__


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


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


class Solution:

	def removeZeroSumSublists(self, head: ListNode) -> ListNode:
		root = ListNode(next=head)
		(r, h) = (root, head)
		while h:
			if not h.val:
				r.next = h.__next__
				h = h.__next__
			else:
				(p, q) = (root, root.__next__)
				while q != h:
					q.val += h.val
					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__)
		(p, q) = (root, root.__next__)
		while q:
			p.val -= q.val
			(p, q) = (q, q.__next__)
		return root.__next__


class Solution:

	def removeZeroSumSublists(self, head: ListNode) -> ListNode:
		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


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


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)