पायथन में यादृच्छिक सूचक के साथ सूची की प्रतिलिपि बनाएँ

एक लिंक्ड सूची एक रैखिक डेटा संरचना है जिसमें प्रत्येक नोड में दो ब्लॉक होते हैं जैसे कि एक ब्लॉक में नोड का मान या डेटा होता है और दूसरे ब्लॉक में अगले फ़ील्ड का पता होता है।

आइए मान लें कि हमारे पास एक लिंक्ड सूची है जैसे कि प्रत्येक नोड में एक यादृच्छिक सूचक होता है जो सूची में अन्य नोड्स को इंगित कर रहा है। कार्य सूची को मूल सूची के समान बनाना है। सूची को मूल सूची से कॉपी करना जिसमें कुछ यादृच्छिक सूचक होते हैं, उसे लिंक की गई सूची की 'डीप कॉपी' कहा जाता है।

उदाहरण के लिए

इनपुट-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