Sao chép Linked List với con trỏ ngẫu nhiên trong C++

Linked List có node chứa data và con trỏ random trỏ đến node khác. Tạo bản sao sâu (deep copy) với cấu trúc giống hệt.

Ví dụ

Output: 5-> 2 -> 3 -> 7 -> 4 ->

Cách tiếp cận: 3 bước

1. Chèn node mới (copy) sau mỗi node gốc
2. Gán con trỏ random cho node mới: newNode->random = oldNode->random->next
3. Tách 2 list: list gốc và list copy

Code C++

#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;
    // B1: Chèn node copy sau mỗi node gốc
    listnode* curr = head;
    while (curr) {
        listnode* newHead = new listnode(curr->data);
        newHead->next = curr->next;
        curr->next = newHead;
        curr = curr->next->next;
    }
    // B2: Gán random pointer
    curr = head;
    while (curr) {
        if (curr->random) (curr->next)->random = (curr->random)->next;
        curr = curr->next->next;
    }
    // B3: Tách 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);
    // Setup random pointers...
    cout << "Original list:" << endl; print(head);
    listnode* deep_copy = copyRandomList(head);
    cout << "Deep Copy:" << endl; print(deep_copy);
    return 0;
}

Kết quả

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