Amazon Interview Question
Software Engineer / DevelopersToo hard for me to grasp. Anyone could come forward to help me out solving this technique? Thanks.
This method needs the list to be traversed 3 times,
Just wondering can we not do it in single pass...?
shouldn't original->next->random = original->random->next;
be
original->next->random = original->random;
saw the answer somewhere else few days back
1) create new link list and copy the data field and next pointer of the original link list.
2) not redirect the next pointer of each node of the original list to the corresponding node in new list'
3)new_node->random_prt = old_node->random_prt->next
The key is to keep one-to-one relationship between the old list and the new list, either through hash or simply build two arrays to keep track.
Then when building the new list, copy val and set next prt properly to new next added node make new_node->random_ptr = old_node->random_ptr, ie new node's random ptr points to the old list as the new list is not completed yet.
Finally, using the saved one-to-one relationship, modify the random_ptr of new_node to the correct new node in the list
in reply to msd....in your approach are all the random pointers remain same as in the original list
One more solution:
1. Create a copy of input by just following the next pointer
2. But when you are copying just keep on doing 2 things.
(i) Make sure that arbit pointer of the new node points to corresponding old node.
A' -> arbit = A
(ii) And the next pointer of old node point to the corresponding new node
A->next = A'
where A is old node and A' is new node.
3. Now traverse the new list again and do the below steps :
A'->arbit = A'->arbit->arbit->next;
A->next = A' ->next->arbit.
1) Create the copy of every node in the list and insert it in original list between current and next node.
- MSD May 26, 2011create 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->next;
/*Traverse two nodes in every iteration*/
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;