Sửa con trỏ ngẫu nhiên trong danh sách liên kết kép trong C++

Trong hướng dẫn này, chúng ta sẽ thảo luận về chương trình sửa con trỏ ngẫu nhiên trong danh sách liên kết kép.

Chúng ta sẽ được cung cấp một danh sách liên kết kép có một nút có con trỏ ngẫu nhiên. Nhiệm vụ của chúng ta là sửa chữa phần tử mà con trỏ nên trỏ tới, tức là phần tử tiếp theo của nó.

Ví dụ

#include <bits/stdc++.h>
using namespace std;
//cấu trúc nút cho danh sách liên kết kép
struct node {
    int data;
    node* next;
    node* prev;
};
//tạo nút mới
node* newNode(int data){
    node* temp = new node;
    temp->data = data;
    temp->next = temp->prev = NULL;
    return temp;
}
//sửa con trỏ ngẫu nhiên
void get_cpointer(node*& head){
    if (!head)
        return;
    node* temp = head;
    if (head->next && head->next->prev != head) {
        head->next->prev = head;
        return;
    }
    //thay đổi nếu vị trí không đúng
    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;
    }
}
//in danh sách liên kết kép
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 << "\nDanh sách liên kết không đúng: ";
    printList(head);
    get_cpointer(head);
    cout << "\nDanh sách liên kết đã sửa: ";
    printList(head);
    return 0;
}

Kết quả

Danh sách liên kết không đúng: 1 (-1) 2 (1) 3 (1) 4 (3)
Danh sách liên kết đã sửa: 1 (-1) 2 (1) 3 (2) 4 (3)