Remove Zero Sum Consecutive Nodes from Linked List

We have given a single Linked List we have to consecutively delete all nodes whose sum is equal to zero until there is no such sequence remaining in our Linked List. After removing all such sequences return the head of our linked list. Let us Understand this problem with an Example.

Example: 1

Input: Head = 1-> 2 -> -3 ->4 ->3
Output:  4 -> 3
Note: As Sum([1->2->-3])=0

Example: 2

Input: Head = 1-> 2 -> 3 ->4 -> -7 -> 6
Output:  1-> 2 -> 6
Note: As Sum([3->4->-7])=0

Remove Zero Sum Consecutive Nodes from Linked List

Let us see step by step approach to solve this problem

Create a Map with Integer as Key and Node as Value.
Create a dummy Node and initialize its value and point its next to Head.
Store Dummy Node and its value in HashMap.
Calculate prefix sum of Nodes and check-in Map if it exists then delete all nodes from the current node to that node.
Now return the Next of dummy Node.

Let us see the solution Code of this problem

Remove zero sum consecutive nodes from linked list in C++

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        unordered_map<int, ListNode**> m;

        int sum = 0;
        for (ListNode** PCurrent = &head; *PCurrent; PCurrent = &((*PCurrent)->next)) {
            auto itr = m.find(sum);
            if (itr != m.end()) {
                ListNode** Pprevious = itr->second;
                int tmpSum = sum + (*Pprevious)->val;
                for (ListNode** Pdelete = &((*Pprevious)->next); Pdelete != PCurrent; Pdelete = &((*Pdelete)->next)) {
                    m.erase(tmpSum);
                    tmpSum += (*Pdelete)->val;
                }
                *Pprevious = *PCurrent;
            }
            else {
                m.emplace(sum, PCurrent);
            }

            sum += (*PCurrent)->val;
        }

        auto itr = m.find(sum);
        if (itr != m.end()) {
            ListNode** Pprevious = itr->second;
            *Pprevious = nullptr;
        }

        return head;
    }
};

Remove zero sum consecutive nodes from linked list in Java

Here is the implementation of the problem in Java

class Solution {
    public ListNode removeZeroSumSublists(ListNode head) {
        Map<Integer, ListNode> m = new HashMap();
        
        ListNode temp=head;
        
        
        ListNode dummy= new ListNode(0);
        dummy.next=head;
        
        m.put(0,dummy);
        int sum=0;
        while(temp!=null)
        {
          sum=sum+temp.val;
            if(m.containsKey(sum))
            {
                ListNode x = m.get(sum).next;
              m.get(sum).next=temp.next;  
                
               
                int g=sum;
                while(x!=temp)
                {
                   
                    m.remove(g+x.val);
                     g=g+x.val;
                    x=x.next;
                    
                }
                
                
            }
           else
            m.put(sum,temp);

            
            temp=temp.next;
        }
        
     return dummy.next;   
    }
}