পাইথনে এলোমেলো পয়েন্টার সহ তালিকা অনুলিপি করুন

একটি লিঙ্কযুক্ত তালিকা হল একটি রৈখিক ডেটা কাঠামো যেখানে প্রতিটি নোডে দুটি ব্লক থাকে যেমন একটি ব্লকে নোডের মান বা ডেটা থাকে এবং অন্য ব্লকে পরবর্তী ক্ষেত্রের ঠিকানা থাকে৷

আসুন আমরা ধরে নিই যে আমাদের একটি লিঙ্কযুক্ত তালিকা রয়েছে যাতে প্রতিটি নোডে একটি র্যান্ডম পয়েন্টার থাকে যা তালিকার অন্যান্য নোডের দিকে নির্দেশ করে। কাজ হল মূল তালিকার মতোই তালিকা তৈরি করা। মূল তালিকা থেকে তালিকাটি অনুলিপি করা যাতে কিছু র্যান্ডম পয়েন্টার থাকে তাকে লিঙ্ক করা তালিকার 'ডিপ কপি' বলা হয়।

উদাহরণস্বরূপ

ইনপুট-1:

আউটপুট:

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

ব্যাখ্যা:

আমরা যদি প্রদত্ত লিঙ্কযুক্ত তালিকায় মূল নোডের মান সহ নতুন তালিকা যুক্ত করি এবং মূল লিঙ্কযুক্ত তালিকার র্যান্ডম পয়েন্টারটিকে নতুন তালিকার পরবর্তী নোডের সাথে প্রতিস্থাপন করি, তাহলে এটি 5-> 2->3 -> হয়ে যাবে। 7-> 4->

এই সমস্যা সমাধানের পদ্ধতি

আমাদের কাছে নোড সহ একটি লিঙ্কযুক্ত তালিকা রয়েছে যার ডেটা এবং একটি র্যান্ডম পয়েন্টার রয়েছে। ডেটা এবং র্যান্ডম পয়েন্টার সহ লিঙ্কযুক্ত তালিকার অনুলিপি অর্জন করতে, আমরা প্রথমে প্রতিটি নোডের পরে একই মান সহ নতুন নোড যুক্ত করব। এটি প্রতিটি নোডের পরে একটি ডুপ্লিকেট নোড তৈরি করবে৷

আরম্ভ করার পরে, তালিকায় র্যান্ডম পয়েন্টারের পথটি পরীক্ষা করুন এবং সেই অনুযায়ী নতুন তৈরি নোডে র্যান্ডম পয়েন্টার রাখুন৷

এখন মূল তালিকার প্রতিটি নোডের পরে নতুন তৈরি নোডগুলিকে আলাদা করা লিঙ্কযুক্ত তালিকার একটি গভীর অনুলিপি তৈরি করবে৷

• ডেটা ফিল্ডের সাথে একটি লিঙ্ক করা তালিকা নিন এবং এর র্যান্ডম নোডের ঠিকানায় পয়েন্টার করুন।
• একটি ফাংশন copyRandomList(listnode*head) মূল তালিকার প্রধান নোডকে ইনপুট হিসাবে নেয় এবং তালিকার গভীর অনুলিপি প্রদান করে।
• যদি মাথা খালি থাকে, তাহলে তালিকাটি খালি এবং আমাদেরকেও মাথাটি ফেরত দিতে হবে৷
• এখন মূল তালিকার প্রতিটি নোডের পরে একই মান সহ একটি নতুন নোড প্রবেশ করান৷
• তারপর মূল তালিকা থেকে র্যান্ডম পয়েন্টারটি অনুলিপি করুন এবং নতুন নোডগুলি সন্নিবেশ করুন, যেমন, newnode->next =curr->randomPointer
• পয়েন্টার এবং ডেটা দিয়ে একটি নতুন নোড তৈরি হয়ে গেলে, আমরা তালিকাটি আলাদা করব এবং আউটপুট হিসাবে তালিকাটি ফিরিয়ে দেব।

উদাহরণ

class listnode:
   def __init__(self, data):
      self.data = data
      self.next = None
      self.random = None
def copyRandomList(head):
   if head is None:
      return head
   # Insert a new node with the same value after each node in the original list.
   curr = head
   while curr != None:
      new = listnode(curr.data)
      new.next = curr.next
      curr.next = new
      curr = curr.next.next

   # Now place the randompointer with the newly created node.
   curr = head
   while curr != None:
      curr.next.random = curr.random.next
      curr = curr.next.next

   # Now Let us separate the newly created list from the original list.
   curr = head
   temp = head.next
   while curr.next != None:
      dummyHead = curr.next
      curr.next = curr.next.next
      curr = dummyHead
   return temp
def printList(head):
   curr = head
   while curr != None:
      print(curr.data, " ", curr.random.data)
      curr = curr.next
head = listnode(1)
head.next = listnode(2)
head.next.next = listnode(3)
head.next.next.next = listnode(4)
head.next.next.next.next = listnode(5)
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
print("Original list:\n")
printList(head)
copiedList = copyRandomList(head)
print("\n Deep Copy of the List:")
printList(copiedList)

উপরের কোডটি চালানোর ফলে আউটপুট তৈরি হবে,

আউটপুট

Original list:
1 3
2 1
3 5
4 5
5 2
Deep Copy of the List:
1 3
2 1
3 5
4 5
5 2