nikunjsoni

1171

Mar 20th, 2021
75
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2.  * Definition for singly-linked list.
  3.  * struct ListNode {
  4.  *     int val;
  5.  *     ListNode *next;
  6.  *     ListNode() : val(0), next(nullptr) {}
  7.  *     ListNode(int x) : val(x), next(nullptr) {}
  8.  *     ListNode(int x, ListNode *next) : val(x), next(next) {}
  9.  * };
  10.  */
  11. class Solution {
  12. public:
  13.     ListNode* removeZeroSumSublists(ListNode* head) {
  14.         unordered_map<int, ListNode*> map;
  15.         ListNode *dummy = new ListNode(0, head);
  16.         map[0] = dummy;
  17.         int sum = 0;
  18.         while(head){
  19.             sum += head->val;
  20.             if(map.find(sum) != map.end()){
  21.                 ListNode* curr = map[sum]->next;
  22.                 int tsum = sum + curr->val;
  23.                 while(tsum != sum){
  24.                     map.erase(tsum);
  25.                     curr = curr->next;
  26.                     tsum += curr->val;
  27.                 }
  28.                 map[sum]->next = head->next;
  29.             }
  30.             else{
  31.                 map[sum] = head;
  32.             }
  33.             head = head->next;
  34.         }
  35.         return dummy->next;
  36.     }
  37. };
RAW Paste Data