CareerCup

First pass
>> Copy the basic linked list structure from old list to new list
>> You'll have data and nextLink fields filled properly
>> Hash the data in each node and store the memory address of the node in the buckets
Second pass
>> Examine what data the randomLink points to in the original list.
>> Look up the hash table with data as key and you'd get memory location of the data in the new list.
>> Fill up the randomLink field in the new list accordingly

PS: I think the hint was too big a hint

See answer from here:
tech-queries.blogspot.com.au/2011/04/copy-linked-list-with-next-and-random.html
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;
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;

While doing this, take care of end of list (NULL pointer) and NULL pointer dereference.

I guess there can be no solution with the entire link list, all the data in each node of the link list are the same. it can be done. but not going to be O(n) if all the data in the list are the same

Step1: In first pass using next pointer create a new linked list and also make a map of original reference Vs new reference
Step 2 In second pass using random node if it not null than search in the map and set to random pointer

Step1: In first pass using next pointer create a new linked list and also make a map of original reference Vs new reference
Creating map means that data in the node might not be distinct, so use object reference
Step 2 In second pass using random node if it not null than search in the map and set to random pointer

// creating a clone of the nodes of the list
// the next pointers of the original list will
// be pointing to the corresponding node in the copy list
// the next pointers of the copy list will be
// pointing to the next node of the corresponding node
// in the original list
p = head
while (p != null) {
 q = clone(p)
 q.next = p.next
 p.next = q
 p = q.next
 // random pointer of q points to nowhere at this point
}

// copying random pointers to the copy list
p = head
while (p != null) {
 q = p.random.next
 p.next.random = q
 p = p.next.next
}

// fixing the next pointers in the two lists
p = head
copyhead = p.next
while (p != null) {
 q = p.next
 p.next = q.next
 q.next = p.next.next
 p = p.next
}
return copyhead

Just start with the first node and keep going to the next link and keep copying all the data and pointers.