मान लीजिए हमारे पास एक सर्कुलर लिंक्ड लिस्ट का एक नोड है जो बढ़ते क्रम में सॉर्टेड है, हमें एक फ़ंक्शन परिभाषित करना है जो मान insertVal को लिस्ट में सम्मिलित करे ताकि यह एक सॉर्टेड सर्कुलर लिस्ट बनी रहे।
नोड लिस्ट में किसी भी एकल नोड का संदर्भ हो सकता है, और यह आवश्यक रूप से सर्कुलर लिस्ट का पहला मान नहीं हो सकता। यदि सम्मिलन के लिए कई उपयुक्त स्थान हैं, तो हम किसी भी स्थान को चुन सकते हैं। यदि लिस्ट खाली है, तो हमें एक नई एकल सर्कुलर लिस्ट बनानी होगी और उस एकल नोड का संदर्भ लौटाना होगा। अन्यथा, हमें मूल दिया गया नोड लौटाना चाहिए।
हल करने की विधि
हम निम्न चरणों का पालन करेंगे:
- यदि हेड null है, तो मान के साथ नया नोड बनाएं, उसका next खुद पर सेट करें, और लौटाएं।
- अन्यथा:
- curr = head->next, prev = head लें।
- मान के साथ नया नोड temp बनाएं।
- done = false।
- अनंत लूप चलाएं:
- यदि curr->val >= val और prev->val <= val, तो temp को prev और curr के बीच सम्मिलित करें, done = true, ब्रेक।
- यदि prev->val > curr->val (रैप-अराउंड बिंदु), तो यदि prev->val <= val या val <= curr->val, तो temp को सम्मिलित करें, done = true, ब्रेक।
- यदि curr == head, तो ब्रेक।
- prev = curr, curr = curr->next।
- यदि done false है, तो temp को हेड के बाद सम्मिलित करें और हेड को temp पर सेट करें।
- हेड लौटाएं।
उदाहरण
बेहतर समझ के लिए निम्न कार्यान्वयन देखें:
#include <bits/stdc++.h> using namespace std; class Node { public: int val; Node* next; Node() {} Node(int _val) { val = _val; next = NULL; } Node(int _val, Node* _next) { val = _val; next = _next; } }; class Solution { public: Node* insert(Node* head, int val) { if(!head){ head = new Node(val); head->next = head; } else{ Node* curr = head->next; Node* prev = head; Node* temp = new Node(val); bool done = false; while(1){ if (curr->val >= val && prev->val <= val) { prev->next = temp; temp->next = curr; done = true; break; } if (prev->val > curr->val) { if (prev->val <= val || val <= curr->val) { prev->next = temp; temp->next = curr; done = true; break; } } if (curr == head) break; prev = curr; curr = curr->next; } if(!done){ temp->next = head; prev->next = temp; head = temp; } } return head; } }; main(){ Solution ob; Node *head = new Node(3); head->next = new Node(4); head->next->next = new Node(1, head); ob.insert(head, 2); Node *temp = head; if (head != NULL){ do{ cout << temp->val << " "; temp = temp->next; } while (temp != head); } }
इनपुट
node *head = new Node(3); head->next = new Node(4); head->next->next = new Node(1, head); insertVal = 2
आउटपुट
3 4 1 2
