CareerCup

1) Create the copy of every node in the list and insert it in original list between current and next node.
create the copy of A and insert it between A & B..
create the copy of B and insert it between B & C..
Continue in this fashion, add the copy of N to Nth node.
2) Now copy the arbitrary link in this fashion

original->next->random = original->random->next;
/*Traverse two nodes in every iteration*/

3) Now restore the original and copy linked lists in this fashion in a single loop.
original->next = original->next->next;
copy->next = copy->next->next;

saw the answer somewhere else few days back

1) create new link list and copy the data field and next pointer of the original link list.
2) not redirect the next pointer of each node of the original list to the corresponding node in new list'
3)new_node->random_prt = old_node->random_prt->next

The key is to keep one-to-one relationship between the old list and the new list, either through hash or simply build two arrays to keep track.

Then when building the new list, copy val and set next prt properly to new next added node make new_node->random_ptr = old_node->random_ptr, ie new node's random ptr points to the old list as the new list is not completed yet.

Finally, using the saved one-to-one relationship, modify the random_ptr of new_node to the correct new node in the list

can't we just copy the nodes in two passes? In the first pass, copy the next pointers and in the second pass, copy the random pointers.

in reply to msd....in your approach are all the random pointers remain same as in the original list

i didn't understand abc comments
i think msd solution was right.
Can you please elaborate ...

One more solution:
1. Create a copy of input by just following the next pointer
2. But when you are copying just keep on doing 2 things.
(i) Make sure that arbit pointer of the new node points to corresponding old node.
A' -> arbit = A
(ii) And the next pointer of old node point to the corresponding new node
A->next = A'
where A is old node and A' is new node.

3. Now traverse the new list again and do the below steps :
A'->arbit = A'->arbit->arbit->next;
A->next = A' ->next->arbit.