คัดลอกรายการด้วยตัวชี้สุ่มใน C++

รายการที่เชื่อมโยงเป็นโครงสร้างข้อมูลเชิงเส้นซึ่งแต่ละโหนดมีสองบล็อก โดยที่หนึ่งบล็อกมีค่าหรือข้อมูลของโหนด และอีกบล็อกมีที่อยู่ของฟิลด์ถัดไป

สมมติว่าเรามีรายการที่เชื่อมโยง โดยที่แต่ละโหนดมีตัวชี้สุ่มซึ่งชี้ไปยังโหนดอื่นในรายการ ภารกิจคือการสร้างรายการให้เหมือนกับรายการเดิม การคัดลอกรายการจากรายการต้นฉบับซึ่งมีตัวชี้แบบสุ่มเรียกว่า 'Deep Copy' ของรายการที่เชื่อมโยง

ตัวอย่าง

อินพุต-1

ผลลัพธ์:

5-> 2 -> 3 -> 7 ->4 ->

คำอธิบาย: หากเราผนวกรายการใหม่ด้วยค่าของโหนดดั้งเดิมในรายการเชื่อมโยงที่กำหนดและแทนที่ตัวชี้สุ่มของรายการที่เชื่อมโยงดั้งเดิมด้วยโหนดถัดไปในรายการใหม่ มันจะกลายเป็น 5-> 2->3 -> 7-> 4->

แนวทางในการแก้ปัญหานี้

เรามีรายการที่เชื่อมโยงกับโหนดที่มีข้อมูลและตัวชี้แบบสุ่ม เพื่อให้ได้สำเนาของรายการที่เชื่อมโยงกับข้อมูลและตัวชี้แบบสุ่ม ก่อนอื่นเราจะต่อท้ายโหนดใหม่ด้วยค่าเดียวกันหลังจากแต่ละโหนด สิ่งนี้จะสร้างโหนดที่ซ้ำกันหลังจากแต่ละโหนด

หลังจากการเริ่มต้น ให้ตรวจสอบเส้นทางของตัวชี้สุ่มในรายการ และวางตัวชี้สุ่มตามนั้นในโหนดที่สร้างขึ้นใหม่

ตอนนี้การแยกโหนดที่สร้างขึ้นใหม่หลังจากแต่ละโหนดในรายการดั้งเดิมจะสร้างสำเนาของรายการที่เชื่อมโยงอย่างลึกซึ้ง

• นำรายการที่เชื่อมโยงพร้อมช่องข้อมูลและตัวชี้ไปยังที่อยู่ของโหนดสุ่ม
• ฟังก์ชัน copyRandomList(listnode*head) รับโหนดส่วนหัวของรายการดั้งเดิมเป็นอินพุตและส่งคืนสำเนาแบบลึกของรายการ
• หากส่วนหัวว่างเปล่า แสดงว่ารายการนั้นว่างเปล่า และเราต้องส่งคืนส่วนหัวด้วย
• ตอนนี้แทรกโหนดใหม่ที่มีค่าเดียวกันหลังจากแต่ละโหนดของรายการเดิม
• จากนั้นคัดลอกตัวชี้สุ่มจากรายการต้นฉบับและแทรกโหนดใหม่ นั่นคือ newnode->next =curr->randomPointer
• เมื่อสร้างโหนดใหม่ด้วยตัวชี้และข้อมูล เราจะแยกรายการและส่งคืนรายการเป็นผลลัพธ์

ตัวอย่าง

#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;
}

การเรียกใช้โค้ดด้านบนจะสร้างผลลัพธ์เป็น

ผลลัพธ์

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