একটি লিঙ্কযুক্ত তালিকা হল একটি রৈখিক ডেটা কাঠামো যেখানে প্রতিটি নোডে দুটি ব্লক থাকে যেমন একটি ব্লকে নোডের মান বা ডেটা থাকে এবং অন্য ব্লকে পরবর্তী ক্ষেত্রের ঠিকানা থাকে৷
আসুন আমরা ধরে নিই যে আমাদের একটি লিঙ্কযুক্ত তালিকা রয়েছে যাতে প্রতিটি নোডে একটি এলোমেলো পয়েন্টার থাকে যা তালিকার অন্যান্য নোডের দিকে নির্দেশ করে। মূল তালিকার মতোই তালিকাটি তৈরি করাই কাজ। মূল তালিকা থেকে তালিকাটি অনুলিপি করা যাতে কিছু র্যান্ডম পয়েন্টার থাকে তাকে লিঙ্ক করা তালিকার 'ডিপ কপি' বলা হয়।
উদাহরণস্বরূপ
ইনপুট-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
