लिंक्ड लिस्ट एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड के दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरा ब्लॉक अगले फील्ड का पता रखता है।
मान लीजिए हमारे पास एक लिंक्ड लिस्ट है जैसे कि प्रत्येक नोड में एक रैंडम पॉइंटर होता है जो लिस्ट में अन्य नोड्स की ओर इंगित करता है। कार्य मूल लिस्ट के समान ही लिस्ट का निर्माण करना है। मूल लिस्ट से लिस्ट की कॉपी करना जिसमें कुछ रैंडम पॉइंटर होते हैं, लिंक्ड लिस्ट की 'डीप कॉपी' कहलाती है।
उदाहरण के लिए
इनपुट-1
आउटपुट:
5-> 2 -> 3 -> 7 ->4 ->
व्याख्या: यदि हम दी गई लिंक्ड लिस्ट में मूल नोड्स के मान के साथ नई लिस्ट को जोड़ते हैं और मूल लिंक्ड लिस्ट के रैंडम पॉइंटर को नई लिस्ट में अगले नोड से बदलते हैं, तो यह 5-> 2-> 3-> 7-> 4-> बन जाएगी।
इस समस्या को हल करने का दृष्टिकोण
हमारे पास डेटा और रैंडम पॉइंटर वाले नोड्स के साथ एक लिंक्ड लिस्ट है। लिंक्ड लिस्ट की डेटा और रैंडम पॉइंटर के साथ कॉपी प्राप्त करने के लिए, हम पहले प्रत्येक नोड के बाद उसी मान के साथ नया नोड जोड़ेंगे। यह प्रत्येक नोड के बाद डुप्लिकेट नोड बनाएगा।
आरंभीकरण के बाद, लिस्ट में रैंडम पॉइंटर का पथ जांचें और नए बनाए गए नोड में रैंडम पॉइंटर को तदनुसार रखें।
अब मूल लिस्ट में प्रत्येक नोड के बाद नए बनाए गए नोड्स को अलग करने से लिंक्ड लिस्ट की डीप कॉपी बनेगी।
- डेटा फील्ड और उसके रैंडम नोड के पते के पॉइंटर के साथ एक लिंक्ड लिस्ट लें।
- एक फ़ंक्शन copyRandomList(listnode*head) मूल लिस्ट के हेड नोड को इनपुट के रूप में लेता है और लिस्ट की डीप कॉपी लौटाता है।
- यदि हेड खाली है, तो लिस्ट खाली है और हमें हेड भी लौटाना होगा।
- अब मूल लिस्ट के प्रत्येक नोड के बाद उसी मान के साथ नया नोड डालें।
- फिर मूल लिस्ट से रैंडम पॉइंटर कॉपी करें और नए नोड्स डालें, यानी newnode->next = curr->randomPointer
- एक बार पॉइंटर और डेटा के साथ नया नोड बन जाने पर, हम लिस्ट को अलग करेंगे और आउटपुट के रूप में लिस्ट लौटाएंगे।
उदाहरण
#include <bits/stdc++.h>
using namespace std;
struct listnode {
int data;
listnode * next, * random;
listnode(int d) {
data = d;
next = NULL;
random = NULL;
}
};
void print(listnode * head) {
listnode * curr = head;
while (curr) {
cout << curr -> data << " " << curr -> random -> data << endl;
curr = curr -> next;
}
}
listnode * copyRandomList(listnode * head) {
if (!head) {
return head;
}
// मूल लिस्ट में प्रत्येक नोड के बाद उसी मान के साथ नया नोड डालें।
listnode * curr = head;
while (curr) {
listnode * newHead = new listnode(curr -> data);
newHead -> next = curr -> next;
curr -> next = newHead;
curr = curr -> next -> next;
}
// अब नए बनाए गए नोड के साथ रैंडम पॉइंटर रखें।
curr = head;
while (curr) {
if (curr -> random)
(curr -> next) -> random = (curr -> random) -> next;
curr = curr -> next -> next;
}
// अब नए बनाए गए लिस्ट को अलग करें
curr = head;
listnode * result = curr -> next;
listnode * dummyHead = new listnode(-1);
dummyHead -> next = result;
while (curr) {
curr -> next = result -> next;
curr = curr -> next;
if (curr) {
result -> next = curr -> next;
}
result = result -> next;
}
result = dummyHead -> next;
delete dummyHead;
return result;
}
int main() {
listnode * head = new listnode(5);
head -> next = new listnode(6);
head -> next -> next = new listnode(3);
head -> next -> next -> next = new listnode(4);
head -> next -> next -> next -> next = new listnode(2);
head -> random = head -> next -> next;
head -> next -> random = head;
head -> next -> next -> random = head -> next -> next -> next -> next;
head -> next -> next -> next -> random = head -> next -> next -> next -> next;
head -> next -> next -> next -> next -> random = head -> next;
cout << "Original list :" << endl;
print(head);
cout << "Deep Copy of the List:" << endl;
listnode * deep_copyList = copyRandomList(head);
print(deep_copyList);
return 0;
}
उपरोक्त कोड चलाने से आउटपुट इस प्रकार उत्पन्न होगा,
आउटपुट
Original List: 5 3 6 5 3 2 4 2 2 6 Deep Copy of the List: 5 3 6 5 3 2 4 2 2 6
