मान लीजिए हमें एक लिंक्ड लिस्ट का हेड दिया गया है; हमें लगातार नोड्स के अनुक्रमों को बार-बार हटाना है जिनका योग 0 है जब तक ऐसा कोई अनुक्रम न रहे। ऐसा करने के बाद, हमें अंतिम लिंक्ड लिस्ट का हेड लौटाना है। तो अगर लिस्ट [1,2,-3,3,1] है, तो परिणाम [3,1] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे:
डमी नामक एक नोड बनाएं, और इसमें 0 स्टोर करें, डमी का नेक्स्ट := हेड सेट करें
एक मैप m बनाएं, कुंजी 0 के लिए m में डमी स्टोर करें, sum = 0 सेट करें
जब तक हेड नल नहीं है:
sum := sum + हेड का मान, m[sum] := हेड सेट करें, और हेड := हेड का नेक्स्ट
हेड := डमी
sum := 0
जब तक हेड नल नहीं है:
sum := sum + हेड का मान
temp := m[sum]
यदि 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]
