C++-এ ডাবলি লিঙ্কড লিস্টে র‍্যান্ডম পয়েন্টার সংশোধন (Correct Random Pointer in Doubly Linked List)

এই টিউটোরিয়ালে, একটি ডাবলি লিঙ্কড লিস্ট দেওয়া থাকে যেখানে একটি নোডের র‍্যান্ডম পয়েন্টার (prev পয়েন্টার) ভুল নির্দেশ করছে। সেটি সংশোধন করে ঠিক পরবর্তী নোডে নির্দেশ করাতে হবে।

C++ প্রোগ্রাম উদাহরণ

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

struct node {
    int data;
    node* next;
    node* prev;
};

node* newNode(int data) {
    node* temp = new node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    return temp;
}

void get_cpointer(node*& head) {
    if (!head) return;
    node* temp = head;
    
    // হেডের next-এর prev যদি হেড না হয়
    if (head->next && head->next->prev != head) {
        head->next->prev = head;
        return;
    }
    
    // হেডের prev যদি NULL না হয়
    if (head->prev != NULL) {
        head->prev = NULL;
        return;
    }
    
    temp = temp->next;
    while (temp) {
        if (temp->next && temp->next->prev != temp) {
            temp->next->prev = temp;
            return;
        } else if (temp->prev && temp->prev->next != temp) {
            temp->prev->next = temp;
            return;
        }
        temp = temp->next;
    }
}

void printList(node* head) {
    node* temp = head;
    while (temp) {
        cout << temp->data << " (";
        cout << (temp->prev ? temp->prev->data : -1) << ") ";
        temp = temp->next;
    }
    cout << endl;
}

int main() {
    node* head = newNode(1);
    head->next = newNode(2);
    head->next->prev = head;
    head->next->next = newNode(3);
    head->next->next->prev = head; // ভুল: 3-এর prev হেড নির্দেশ করছে
    head->next->next->next = newNode(4);
    head->next->next->next->prev = head->next->next;
    
    cout << "Incorrect Linked List: ";
    printList(head);
    
    get_cpointer(head);
    
    cout << "Corrected Linked List: ";
    printList(head);
    return 0;
}

আউটপুট

Incorrect Linked List: 1 (-1) 2 (1) 3 (1) 4 (3)
Corrected Linked List: 1 (-1) 2 (1) 3 (2) 4 (3)