LeetCode/1171.cpp at main · HungDongne/LeetCode · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution
{
public:
    Solution()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        cout.tie(nullptr);
    }
    ListNode *removeZeroSumSublists(ListNode *head)
    {
        ListNode dummy(0, head);
        int prefix = 0;
        unordered_map<int, ListNode *> prefixToNode;
        prefixToNode[0] = &dummy;

        for (; head; head = head->next)
        {
            prefix += head->val;
            prefixToNode[prefix] = head;
        }

        prefix = 0;

        for (head = &dummy; head; head = head->next)
        {
            prefix += head->val;
            head->next = prefixToNode[prefix]->next;
        }

        return dummy.next;
    }
};