एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड में दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरे ब्लॉक में अगले फ़ील्ड का पता होता है।
आइए मान लें कि हमारे पास एक लिंक्ड सूची है जैसे कि प्रत्येक नोड में एक यादृच्छिक सूचक होता है जो सूची में अन्य नोड्स को इंगित कर रहा है। कार्य सूची को मूल सूची के समान बनाना है। मूल सूची से सूची की प्रतिलिपि बनाना जिसमें कुछ यादृच्छिक सूचक होते हैं, उसे लिंक की गई सूची की 'डीप कॉपी' कहा जाता है।
उदाहरण के लिए
इनपुट-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;
}
//Insert a new node with the same value after each node in the original list.
listnode * curr = head;
while (curr) {
listnode * newHead = new listnode(curr -> data);
newHead -> next = curr -> next;
curr -> next = newHead;
curr = curr -> next -> next;
}
//Now place the randompointer with the newly created node.
curr = head;
while (curr) {
if (curr -> random)
(curr -> next) -> random = (curr -> random) -> next;
curr = curr -> next -> next;
}
//Now Let us separate the newly created list
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