struct Node {
int data;
Node * next;
Node * random;
} where data is the data, next is a pointer to the next node in the list and random is a pointer to any other node in the list. The random pointer may NOT point to unique nodes in the list, which means many random pointers of different nodes could point to a same node.
Create a copy of this linked list.
4 comments:
My answer :-
Brute force approach
1. First traversal of the OLD_LIST, as you go on creating a linked list create a mapping (serial_number_of_curr_node, serial_number_of_random_node)
eg (1,5) means the node number 1 has the random field which points to node number 5.
2. Second traversal :- fill the random field of the new node.
But this requires an array to store the mapping. It seems it can be done without using any mapping information.
Most obvious answer would be to use a queue or a stack, depending on your preference between DFS and BFS.
As you can see, this is a graph, which is masquerading as a linked list. And from what I know, it's impossible to traverse a graph without maintaining some data structure for visited, done, etc. So, initiate a BFS, and start copying.
Excellent answer dude...!
The good old days of programming philosophy :).
Actually I think it can be done without O(N) space, at the cost of more time.
1) O(N) space, O(N) time.
From the start node, start the random graph traversal, set visited flag as mentioned. If you encounter a visited flag, that means we are in a cycle.
So start = start->next.
Then redo random traversal only if the current start has not been visited. Otherwise just next, next. I think this is the solution Teju mentioned.
2) O(N*N) time, O(constant) space.
Just traverse using just next pointer and create new list..
Now the job is to create the random pointers.
From start node, see
random_ptr = start->random.
Now in old list from start node, just iterate until you hit random_ptr. This will give you the number of times you have to do next, to get the random pointer.
So just do the same in the new list, and populate the random pointers.
This is O(N*N) time, and constant addditional space though.
This is different from BFS, DFS, because while you are traversing through the next pointers you are guaranteed not to be in a cycle.
Post a Comment