Remove Zero Sum Consecutive Nodes from Linked List Solutions in C++

/// Source : https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
/// Author : liuyubobobo
/// Time   : 2020-04-11

#include <iostream>
#include <unordered_map>

using namespace std;


/// Brute Force
/// Time Complexity: O(n^2)
/// Space Complexity: O(1)

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        for(ListNode* prev = dummyHead; prev->next;){

            int sum = 0;
            for(ListNode* node = prev->next; node; node = node->next){
                sum += node->val;
                if(sum == 0){
                    prev->next = node->next;
                    break;
                }
            }
            if(sum) prev = prev->next;
        }
        return dummyHead->next;
    }
};


int main() {

    return 0;
}

/// Source : https://leetcode.com/problems/remove-zero-sum-consecutive-nodes-from-linked-list/
/// Author : liuyubobobo
/// Time   : 2019-08-25
/// Updated: 2020-04-11

#include <iostream>
#include <unordered_map>

using namespace std;


/// Using HashMap
/// Time Complexity: O(n)
/// Space Complexity: O(n)

/// Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {

        ListNode* dummyHead = new ListNode(0);
        dummyHead->next = head;

        unordered_map<int, ListNode*> map;
        ListNode* cur = dummyHead;
        int presum = 0;
        while(cur){
            presum += cur->val;
            if(map.count(presum)){

                int erase_sum = presum;
                for(ListNode* node = map[presum]->next; node != cur; node = node->next){
                    erase_sum += node->val;
                    map.erase(erase_sum);
                }
                map[presum]->next = cur->next;
            }
            else
                map[presum] = cur;
            cur = cur->next;
        }
        return dummyHead->next;
    }
};


int main() {

    return 0;
}