Hi,

First of all this is not a homework, this is an interview question that I got from a company I attended today.

You have a singly linked list with the Node structure as the following

class Node{
    int data;
    Node next;
    Node random;
}

You have a typical singly linked list of length n. The random pointer in each node in the linkedlist randomly points to some Node within the linked list. The Question is to create a copy of the linked list efficiently into a different LinkedList.

I said that I will first calculate the Random pointer's position in the linked list and store it in an array. Then create a new linked list normally. Then iterate through the linked list by setting the random pointer where they belong by reading the values stored from the array. I know its a very brute force technique and the interviewer asked me to come up with a better solution but I couldnt.

Please can someone answer this? I can explain if the question is not clear.