LeetCode- 1171. Remove Zero Sum Consecutive Nodes from Linked List

Problem statement :-

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.

Example

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

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

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

Solution

We Initialize dummy head with current head and initialize cumulative sum variable and a dictionary to keep track of cumulative sum across all the heads.

curr = head
cumsum = 0
sum_dict = {}
while curr:
  cumsum += curr.val

If cumulative sum is 0 so we have to delete all the nodes previous to this including the current node so we set current to next and delete all the nodes starting from the original head to the current head and reinitialize all the variables and the dictionary.

if cumsum == 0:
  curr = curr.next
  while head != curr:
    delNode = head
    head = head.next
    del delNode
    curr = head
    cumsum = 0
    sum_dict = {}

If current cumulative sum is already present in the dictionary that means we have to delete all the nodes between previous occurrence of current sum and current node including So first we start from the previous node, assign current to the next and we start deleting from previous until we have reached the current.

elif cumsum in sum_dict:
  prv = sum_dict[cumsum]
  curr = curr.next
  while prv.next != curr:
      delNode = prv.next
      prv.next = delNode.next
      del delNode
  curr = head
  cumsum = 0
  sum_dict = {}

If the sum is not present we store it with respect to the current node

else:
  sum_dict[cumsum] = curr
  curr = curr.next

Here is the full

class Solution:
    def removeZeroSumSublists(self, head):
        curr = head
        cumsum = 0
        sum_dict = {}
        while curr:
            cumsum += curr.val
            if cumsum == 0:
                curr = curr.next
                while head != curr:
                    delNode = head
                    head = head.next
                    del delNode
                curr = head
                cumsum = 0
                sum_dict = {}
            elif cumsum in sum_dict:
                prv = sum_dict[cumsum]
                curr = curr.next
                while prv.next != curr:
                    delNode = prv.next
                    prv.next = delNode.next
                    del delNode
                curr = head
                cumsum = 0
                sum_dict = {}
            else:
                sum_dict[cumsum] = curr
                curr = curr.next
        return head