CareerCup

I was asked similar question and I failed to solve this

Clone a link list in which every node has two pointers: one pointer points to next node, and the other pointer points to some random node in the same list.

Solution:
step1:for every node, clone a node and add it to the list as the next node;
step2:for each odd-number node, change the ref pointer to the next node of the node it points ti
step3: split even-number nodes and odd-number nodes into two lists. The list which contains the odd-number nodes is the clone of the original list.

Simple solution
Create a hashmap of Original address of node and corresponding cloned node's address.
After the clone list is ready, use the reference pointer as the key to hashmap. The value is the address of the node in cloned list.

not very clear about the question. explicitly set it to NULL or point to the same object as the original one?

They can be any two pointers to other nodes..The only thing we have to be careful while copying the pointers is that we could have visited a previously visited node.so we need to have something like a hash map.

Can you clarify this question?

What does the *reference struct member do ?

reference pointer point to a arbitary node in the same linklist (i.e) a reference pointer in 2nd node can point to 7th node of the same list.
Now if we have to clone this list, while cloning second node you will now have to point the reference pointer to 7th node which is still not created as you are still in process of cloing 2nd node.
Now the question is how do you fill up all reference nodes with address that are not created, and also if some 4th node reference points to 2nd node, you still need to know that it points to 2nd node to fill this reference.

I hope this clarifies the quesiton.