Linked List एक linear data structure है जिसमें प्रत्येक node के दो blocks होते हैं जैसे कि एक block में node का value या data होता है और दूसरे block में next field का address होता है।
मान लीजिए हमारे पास एक linked list है जैसे कि प्रत्येक node में एक random pointer होता है जो list में अन्य nodes को point कर रहा है। Task है original list के समान list construct करना। Original list से copy करना जिसमें कुछ random pointer हो, linked list की 'Deep Copy' कहलाती है।
उदाहरण के लिए
Input-1:
Output:
5-> 2 -> 3 -> 7 ->4 ->
व्याख्या:
यदि हम new list को original nodes के value के साथ append करते हैं और original linked list के random pointer को new list में next node से replace करते हैं, तो यह 5-> 2-> 3-> 7-> 4-> बन जाएगा।
Problem हल करने का दृष्टिकोण
हमारे पास data field और random pointer वाले nodes के साथ एक linked list है। Linked list की copy achieve करने के लिए data और random pointer के साथ, हम पहले प्रत्येक node के बाद same value के साथ new node append करेंगे। यह प्रत्येक node के बाद duplicate node create करेगा।
Initialization के बाद, list में random pointer का path check करें और newly created node में random pointer accordingly place करें।
अब original list में प्रत्येक node के बाद newly created nodes को separate करने से Linked List की deep copy बनेगी।
- Data field और random node के address के pointer के साथ linked list लें।
- एक function copyRandomList(listnode* head) original list के head node को input के रूप में लेता है और list की deep copy return करता है।
- यदि head empty है, तो list empty है और हमें head भी return करना होगा।
- अब original list के प्रत्येक node के बाद same value के साथ new node insert करें।
- फिर original list से random pointer copy करें और new nodes insert करें, यानी newnode->next = curr->randomPointer
- एक बार new node pointer और data के साथ बन जाने पर, हम list separate करेंगे और output के रूप में list return करेंगे।
उदाहरण
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)
उपरोक्त code चलाने से output generate होगा:
आउटपुट
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
