use hash map...with key as original node and value as duplicate of this node ....duplicate node next and random pointer is set to NULL initially. now traverse whole linked list keep on adding node. after this do another traversal of orig linked list ....taking key as orig node ..duplicate=fetch value at this key(orig) make duplicate node next and random ptr to duplicate->next=fetch_value_from_hash(orig->next) duplicate->random=fetch_value_from_hash(orig->random)
On Tue, Oct 23, 2012 at 2:06 PM, saket <narayan.shiv...@gmail.com> wrote: > There is one linked list having two pointer one as usual next and other is > random pointer pointing to any random node in list. > write algo to make a duplicate of it. > Note:- Original list is const, Can't be modified. > i know O(n) solution when list can be modified , and o(n^2) when list can > be modified. > any one with O(n) solution when list couldnt be modified . > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To view this discussion on the web visit > https://groups.google.com/d/msg/algogeeks/-/5RLLbA5iod0J. > To post to this group, send email to algogeeks@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
