copy a linked list with next and random pointer, only read privileges are given on list

Question

I need to copy a linked list with next and random pointer.The next pointer as usual points to the next element in the linked list and the random pointer might point to any of the other node or even on itself. How can this be done if I am not allowed to modify the given list at any time, only read privileges are given on the list.

Answer 1

Elegant solution (linear time, constant space):

Create copies of Node 1, 2, 3...n and insert them between 1 and 2, 2 and 3 and so on, ignoring the random field for now. So there are 2n nodes total in the list.

Now set the value of random fields in the new nodes in the following way with a single pass:

original.next.random = original.random.next

This works, because LHS is the random field in the newly created node, and RHS is the pointer to the arbitrary's node's copy, exactly what we wanted.

Now restore the original linked list in a single pass, and return the new list.

original.next = original.next.next;
copy.next = copy.next.next; 

The solution is taken from here.

Answer 2

The simplest solution would be something like this...

You traverse the original linked list and create another linked list, whose nodes are the same as in the original list, with proper next pointers, pointing to the corresponding nodes of the new list. You keep the random pointers as they are for now.

While you're traversing the list you also put the old list's node address/pointer and the new list's node address/pointer onto an associative array (AKA map, hash table, etc), where the old list's node address/pointer is the key and the new list's node address/pointer is the value.

Then you traverse the new list and replace the random pointer in every node with the value from the associative array corresponding to the key equal to the random pointer.

A hash table can be used as an associative array to achieve time and memory cost proportional to the number of elements in the original list.

The time & space complexity of this solution is O(n) each.

Answer 3

struct node * copy(struct node * head) 
{
   struct node *dummy;
   struct node *dummy1=dummy;
   struct node *head1=head;

   struct node *map[1000000];
   while(head) {
      dummy->next=new struct node;
      map[head]=dummy->next;
      dummy->next->data=head->data;
      dummy=dummy->next;
      head=head->next
   }
   dummy=dummy1;
   head=head1;
   while(head){
      dummy->next->arb=map[head->arb];
      dummy=dummy->next;
      head=head->next;
   }
   return dummy1->next;
}