C++-এ র‍্যান্ডম পয়েন্টারসহ লিঙ্কড লিস্টের ডিপ কপি (Deep Copy)

র‍্যান্ডম পয়েন্টারযুক্ত লিঙ্কড লিস্টের ডিপ কপি বানাতে হলে নোডগুলো ডুপ্লিকেট করে যেন র‍্যান্ডম পয়েন্টারও সঠিকভাবে নির্দেশ করে।

অ্যালগরিদম (৩ ধাপে)

1. ইন্টারলিভিং: প্রতিটি নোডের পরে তার কপি নোড ইনসার্ট করুন (A→A'→B→B'...)
2. র‍্যান্ডম পয়েন্টার কপি: অরিজিনাল নোডের random→next = কপি নোডের random
3. সেপারেশন: দুটি লিস্ট আলাদা করুন।

উদাহরণ কোড

#include <bits/stdc++.h>
using namespace std;

struct Node {
    int data;
    Node *next, *random;
    Node(int d) : data(d), next(nullptr), random(nullptr) {}
};

Node* copyRandomList(Node* head) {
    if (!head) return nullptr;
    
    // Step 1: Interleave copied nodes
    Node* curr = head;
    while (curr) {
        Node* copy = new Node(curr->data);
        copy->next = curr->next;
        curr->next = copy;
        curr = copy->next;
    }
    
    // Step 2: Copy random pointers
    curr = head;
    while (curr) {
        if (curr->random)
            curr->next->random = curr->random->next;
        curr = curr->next->next;
    }
    
    // Step 3: Separate lists
    curr = head;
    Node* copyHead = head->next;
    while (curr) {
        Node* copy = curr->next;
        curr->next = copy->next;
        curr = curr->next;
        if (curr) copy->next = curr->next;
    }
    return copyHead;
}

int main() {
    // টেস্ট কেস তৈরি করুন...
    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