লিঙ্কড লিস্ট থেকে শূন্য যোগফল বিশিষ্ট কনসেকিউটিভ নোড মুছে ফেলা (C++)

এই সমস্যায় একটি লিঙ্কড লিস্টের হেড দেওয়া আছে। যেসব কনসেকিউটিভ নোডের যোগফল ০, সেগুলো বারবার মুছে ফেলতে হবে যতক্ষণ না এমন সিকোয়েন্স থাকে। শেষে ফাইনাল লিঙ্কড লিস্টের হেড ফেরত দিতে হবে।

উদাহরণ

ইনপুট: [1, 2, -3, 3, 1]

আউটপুট: [3, 1]

অ্যালগরিদম

1. একটি ডামি নোড তৈরি করুন (ভ্যালু ০), এর next = head।
2. একটি unordered_map m রাখুন যেখানে key = প্রিফিক্স সম, value = নোড পয়েন্টার। m[0] = dummy।
3. প্রথম পাস: লিস্ট ট্রাভার্স করে প্রিফিক্স সম ক্যালকুলেট করুন এবং m[sum] = current_node আপডেট করুন। একই সম দुबার পেলে লেটেস্ট নোড স্টোর হবে।
4. দ্বিতীয় পাস: আবার ডামি থেকে শুরু করুন। প্রিফিক্স সম ক্যালকুলেট করুন। temp = m[sum]। যদি temp != current হয়, তবে current->next = temp->next করে মাঝপথের নোডগুলো বাদ দিন।
5. dummy->next ফেরত দিন।

C++ প্রোগ্রাম

#include <bits/stdc++.h>
using namespace std;

class ListNode {
public:
    int val;
    ListNode* next;
    ListNode(int data) : val(data), next(NULL) {}
};

ListNode* make_list(vector<int> v) {
    ListNode* head = new ListNode(v[0]);
    for (int i = 1; i < v.size(); i++) {
        ListNode* ptr = head;
        while (ptr->next) ptr = ptr->next;
        ptr->next = new ListNode(v[i]);
    }
    return head;
}

void print_list(ListNode* head) {
    cout << "[";
    while (head) {
        cout << head->val << ", ";
        head = head->next;
    }
    cout << "]" << endl;
}

class Solution {
public:
    ListNode* removeZeroSumSublists(ListNode* head) {
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        unordered_map<int, ListNode*> m;
        m[0] = dummy;
        int sum = 0;

        // প্রথম পাস: প্রিফিক্স সম স্টোর
        while (head) {
            sum += head->val;
            m[sum] = head;
            head = head->next;
        }

        // দ্বিতীয় পাস: শূন্য-সাম সিকোয়েন্স বাদ দিন
        head = dummy;
        sum = 0;
        while (head) {
            sum += head->val;
            ListNode* temp = m[sum];
            if (temp != head)
                head->next = temp->next;
            head = head->next;
        }
        return dummy->next;
    }
};

int main() {
    vector<int> v1 = {1, 2, -3, 3, 1};
    ListNode* head = make_list(v1);
    Solution ob;
    print_list(ob.removeZeroSumSublists(head));
    return 0;
}

আউটপুট

[3, 1]