Copy a LinkedList that has a Random Pointer in it
- by Bragaadeesh
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.
