ধরুন আমরা একটি লিঙ্কড লিস্টের হেড দিয়েছি; আমাদের বারবার নোডের ক্রমাগত ক্রমগুলি মুছে ফেলতে হবে যেগুলির যোগফল 0 হয় যতক্ষণ না এরকম কোনও সিকোয়েন্স না থাকে। তাই এটি করার পরে, আমাদের চূড়ান্ত লিঙ্কযুক্ত তালিকার প্রধানটি ফেরত দিতে হবে। তাই যদি তালিকাটি [1,2,-3,3,1] এর মত হয়, তাহলে ফলাফল হবে [3,1]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
ডামি নামে একটি নোড তৈরি করুন এবং এতে 0 সংরক্ষণ করুন, ডামির পাশে সেট করুন :=head
-
একটি মানচিত্র m তৈরি করুন, কী 0-এর জন্য m-এ ডামি সংরক্ষণ করুন, যোগফল =0
সেট করুন -
যখন মাথা শূন্য হয় না -
-
যোগফল :=যোগফল + মাথার মান, সেট m[সমষ্টি] :=মাথা, এবং মাথা :=মাথার পাশে
-
-
মাথা :=ডামি
-
যোগফল :=0
-
যখন হেড শূন্য হয় না
-
যোগফল :=যোগফল + মাথার মান
-
temp :=m[সমষ্টি]
-
যদি temp হেড না হয়, তাহলে হেডের পরের :=temp-এর পরের
-
মাথা :=মাথার পাশে
-
-
ডামির পরের দিকে ফিরে যান
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
উদাহরণ
#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 != NULL){ ptr = ptr->next; } ptr->next = new ListNode(v[i]); } return head; } void print_list(ListNode *head){ ListNode *ptr = head; cout << "["; while(ptr){ cout << ptr->val << ", "; ptr = ptr->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; } }; main(){ vector<int> v1 = {1,2,-3,3,1}; ListNode *head = make_list(v1); Solution ob; print_list(ob.removeZeroSumSublists(head)); }
ইনপুট
[1,2,-3,3,1]
আউটপুট
[3,1]