แก้ไข Random Pointer ใน Doubly Linked List ใน C++

ในบทช่วยสอนนี้ เราจะพูดถึงโปรแกรมที่แก้ไข random pointer ใน Doubly Linked List

สำหรับสิ่งนี้ เราจะได้รับ Doubly Linked List ที่มีโหนดหนึ่งมี random pointer งานของเราคือแก้ไของค์ประกอบที่ pointer ควรชี้ไป คือ องค์ประกอบถัดไป

ตัวอย่างโค้ด

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

//node structure for doubly linked list
struct node {
    int data;
    node* next;
    node* prev;
};

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

//correcting the random pointer
void get_cpointer(node*& head){
    if (!head)
        return;
    node* temp = head;
    if (head->next && head->next->prev != head) {
        head->next->prev = head;
        return;
    }
    //changing if the position is incorrect
    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;
    }
}

//printing the doubly linked list
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;
    head->next->next->next = newNode(4);
    head->next->next->next->prev = head->next->next;
    cout << "\nIncorrect Linked List: ";
    printList(head);
    get_cpointer(head);
    cout << "\nCorrected 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)