educative.io

Educative

Copy Linked List with Arbitrary Pointer

def deep_copy_arbitrary_pointer(head):
   # first pass to connect clone nodes as next nodes
   current = head
   while current:
      next = current.next
      clone = LinkedListNode(current.data)
      current.next = clone
      clone.next = next
      current = next
   
   # second pass to connect the arbitrary nodes
   current = head
   while current:
      # if the arbitrary pointer exists, connect the pointer for the cloned node
      if current.arbitrary:
         current.next.arbitrary = current.arbitrary.next
      # move the current pointer two steps to get to the next original node
      current = current.next.next
   
   # third pass to separate the two lists
   new_head = head.next
   current = new_head
   while current and current.next:
      # skip the next node from the first cloned node and start connecting
      current.next = current.next.next
      # move the node pointer to the next node
      current = current.next

   current = new_head
   while current:
      print(current.data)
      current = current.next
   print("first print")

   return new_head

In this code where I am printing the list, it prints it two times on the console for some reason for each input. In one of the print result I can see correct output when I print “new_head” and in the other one the first nodes repeat. I finally get the correct result if I return new_head.next from the code. I don’t understand if this a code issue or a platform issue.

Hi @Nimish_Bajaj
I am unable to understand the problem whose solution you have presented. If you want to want to clone a LinkList, then the most straightforward approach will be

def clone(head):
     obj_linked_list = Linked_List()
     while head is not None:
               obj_linked_list.add_on_tail(head.get_data())
               head = head.get_next()
     return obj_linked_list.get_head()

I haven’t answered your question then please elaborate on the question. Thanks.