Danh sách được liên kết là một cấu trúc dữ liệu tuyến tính trong đó mỗi nút có hai khối sao cho một khối chứa giá trị hoặc dữ liệu của nút và khối còn lại chứa địa chỉ của trường tiếp theo.
Giả sử rằng chúng ta có một danh sách liên kết sao cho mỗi nút chứa một con trỏ ngẫu nhiên trỏ đến các nút khác trong danh sách. Nhiệm vụ là xây dựng danh sách giống với danh sách ban đầu. Việc sao chép danh sách từ danh sách gốc có một số con trỏ ngẫu nhiên được gọi là 'Bản sao sâu' của danh sách được liên kết.
Ví dụ
Đầu vào-1
Đầu ra:
5-> 2 -> 3 -> 7 ->4 ->
Giải thích: Nếu chúng ta nối danh sách mới với giá trị của các nút ban đầu trong danh sách liên kết đã cho và thay thế con trỏ ngẫu nhiên của danh sách liên kết ban đầu bằng nút tiếp theo trong danh sách mới, thì nó sẽ trở thành 5-> 2-> 3 -> 7-> 4->
Phương pháp tiếp cận để giải quyết vấn đề này
Chúng tôi có một danh sách được liên kết với các nút chứa dữ liệu của nó và một con trỏ ngẫu nhiên. Để đạt được bản sao của danh sách liên kết với dữ liệu và con trỏ ngẫu nhiên, trước tiên chúng ta sẽ nối thêm nút mới với cùng một giá trị sau mỗi nút. Thao tác này sẽ tạo một nút trùng lặp sau mỗi nút.
Sau khi khởi tạo, hãy kiểm tra đường dẫn của con trỏ ngẫu nhiên trong danh sách và đặt con trỏ ngẫu nhiên tương ứng vào nút mới tạo.
Bây giờ, việc tách các nút mới được tạo sau mỗi nút trong danh sách ban đầu sẽ tạo ra một bản sao sâu của Danh sách được Liên kết.
- Lấy một danh sách được liên kết với trường dữ liệu và con trỏ đến địa chỉ của nút ngẫu nhiên của nó.
- Một hàm copyRandomList (listnode * head) lấy nút đầu của danh sách gốc làm đầu vào và trả về bản sao sâu của danh sách.
- Nếu phần đầu trống, thì danh sách trống và chúng tôi cũng phải trả lại phần đầu.
- Bây giờ, hãy chèn một nút mới có cùng giá trị sau mỗi nút của danh sách ban đầu.
- Sau đó, sao chép con trỏ ngẫu nhiên từ danh sách ban đầu và chèn các nút mới, tức là newnode-> next =curr-> randomPointer
- Khi một nút mới được tạo bằng con trỏ và dữ liệu, chúng tôi sẽ tách danh sách và trả lại danh sách dưới dạng đầu ra.
Ví dụ
#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;
}
//Insert a new node with the same value after each node in the original list.
listnode * curr = head;
while (curr) {
listnode * newHead = new listnode(curr -> data);
newHead -> next = curr -> next;
curr -> next = newHead;
curr = curr -> next -> next;
}
//Now place the randompointer with the newly created node.
curr = head;
while (curr) {
if (curr -> random)
(curr -> next) -> random = (curr -> random) -> next;
curr = curr -> next -> next;
}
//Now Let us separate the newly created 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);
head -> random = head -> next -> next;
head -> next -> random = head;
head -> next -> next -> random =
head -> next -> next -> next -> next;
head -> next -> next -> next -> random =
head -> next -> next -> next -> next;
head -> next -> next -> next -> next -> random =
head -> next;
cout << "Original list :" << endl;
print(head);
cout << "Deep Copy of the List:" << endl;
listnode * deep_copyList = copyRandomList(head);
print(deep_copyList);
return 0;
} Chạy đoạn mã trên sẽ tạo ra kết quả là,
Đầu ra
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