मान लीजिए कि हमारे पास एक सर्कुलर लिंक्ड लिस्ट से एक नोड है जिसे बढ़ते क्रम में क्रमबद्ध किया गया है, हमें सूची में वैल्यू इंसर्टवैल डालने के लिए एक फ़ंक्शन को परिभाषित करना होगा जैसे कि यह एक क्रमबद्ध सर्कुलर सूची बनी रहे।
नोड सूची में किसी एकल नोड का संदर्भ हो सकता है, और जरूरी नहीं कि यह परिपत्र सूची का पहला मान हो। यदि सम्मिलन के लिए कई उपयुक्त स्थान हैं, तो हम नया मान डालने के लिए कोई भी स्थान चुन सकते हैं। यदि सूची खाली है, तो हमें एक नई एकल परिपत्र सूची बनानी होगी और उस एकल नोड का संदर्भ वापस करना होगा। अन्यथा, हमें दिए गए मूल नोड को वापस कर देना चाहिए।
इसलिए, अगर इनपुट हेड =[3,4,1], इन्सर्टवैल =2, इमेज जैसा है, तो आउटपुट [3,4,1,2], इमेज होगा
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
अगर सिर खाली है, तो -
-
सिर:=वैल के साथ नया नोड
-
सिर के आगे :=सिर
-
-
अन्यथा
-
curr =सिर के आगे
-
पिछला =सिर
-
अस्थायी =वैल के साथ नया नोड
-
किया :=झूठा
-
अनंत लूपिंग करें, करें −
-
अगर वैल इन करंट>=वैल और वैल ऑफ प्रीव <=वैल, तो −
-
पिछला:=अस्थायी के बाद
-
अस्थायी :=वक्र के आगे
-
किया :=सच
-
लूप से बाहर आएं
-
-
अगर पिछले का वैल> करंट का वैल, तो -
-
अगर पिछला का वैल <=वैल या वैल <=कर्व का वैल, तो -
-
पिछला:=अस्थायी के बाद
-
अस्थायी :=वक्र के आगे
-
किया :=सच
-
लूप से बाहर आएं
-
-
-
यदि कर्व सिर के समान है, तो -
-
लूप से बाहर आएं
-
-
पिछला :=वर्तमान
-
curr :=curr के आगे
-
-
अगर किया गलत है, तो -
-
अस्थायी:=सिर के आगे
-
पिछला:=अस्थायी के बाद
-
सिर:=अस्थायी
-
-
-
वापसी सिर
उदाहरण
आइए एक बेहतर समझ प्राप्त करने के लिए निम्नलिखित कार्यान्वयन देखें -
#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