@Sanjeev: Set a pointer p to the first node. Traverse the list. When at the
kth node, set p to the kth node with probability 1/k. When you reach the
end of the list, return p, which will point to a random node with uniform
probability.
Dave
On Thursday, December 27, 2012 11:18:20 PM UTC-6, Sanjeev wrote:
> i mean the length of the linked list is not known to us.
> @udit how can we do this in single traversal ? i think we need to traverse
> the linked list twice in your case.
> Please reply if i am wrong ?
>
> On Thu, Dec 27, 2012 at 10:48 PM, Udit Agarwal <udit...@gmail.com<javascript:>
> > wrote:
>
>> If the length of the linked is infinite then the above algo would do
>> the needful.
>> In case you have a finite length linked list, then you can normalize
>> the random value using following:
>> Suppose length of linked list is: l
>> random number is: r; and r > l
>> then new random number would be: r1 = r%l;
>> now again use the above algo using new random number r1;
>>
>> On Thu, Dec 27, 2012 at 4:12 PM, Vineeth <vineet...@gmail.com<javascript:>>
>> wrote:
>> > You said : "Given a linked list of infinite length"
>> >
>> > On Thu, Dec 27, 2012 at 4:06 PM, naveen shukla
>> > <naveenshukla...@gmail.com <javascript:>> wrote:
>> >> But suppose a random number generate a value 5 and your linked list
>> has only
>> >> four elements. In that case what would be the answer ???
>> >>
>> >>
>> >> On Thu, Dec 27, 2012 at 4:03 PM, Prem Krishna Chettri <
>> hpre...@gmail.com <javascript:>>
>> >> wrote:
>> >>>
>> >>> Well my algo will be Something like this
>> >>>
>> >>> 1> Get a Random number. Perhaps You can have the function like
>> Randon(List
>> >>> *head, int Randomnumber)
>> >>>
>> >>> 2> Use the function argument Randomnumber to loop the list.
>> >>> i.e. for(int count=0;count<=Randomnumber;count++ ){
>> >>> head = head -> next;
>> >>> }
>> >>>
>> >>> 3> print (head->value);
>> >>>
>> >>> 4> return ;
>> >>>
>> >>> Now as we are using byvalue when we return the value of head remains
>> the
>> >>> same old head value. So everytime we call we are traversing the same
>> old
>> >>> list.
>> >>>
>> >>> The Random variable can be taken inside the function itself if the
>> user
>> >>> is not taking the random value.
>> >>> i.e. int Randomnumber = random(); and now the user can calll Simple
>> >>> Random(head);
>> >>>
>> >>>
>> >>>
>> >>> On Thu, Dec 27, 2012 at 3:31 PM, naveen shukla
>> >>> <naveenshukla...@gmail.com <javascript:>> wrote:
>> >>>>
>> >>>> random node
>> >>>
>> >>>
>> >>> --
>> >>>
>> >>>
>> >>
>> >>
>> >>
>> >>
>> >> --
>> >> With Best Wishes
>> >>
>> >> From:
>> >>
>> >> Naveen Shukla
>> >> IIIT Allahabad
>> >> B.Tech IT 4th year
>> >> Mob No: 07860896972
>> >> E-mail naveenshukla...@gmail.com <javascript:>
>> >>
>> >> --
>> >>
>> >>
>> >
>> > --
>> >
>> >
>>
>>
>>
>> --
>> Udit Agarwal
>> B.Tech. ( Information Technology ) , 7th Semester,
>> Indian Institute of Information Technology
>> Allahabad - 211012, India
>> Email : udit...@gmail.com <javascript:>
>> Mobile: +91-9411656264
>>
>> --
>>
>>
>>
>
>
> --
> With Best Wishes
>
> From:
>
> Naveen Shukla
> IIIT Allahabad
> B.Tech IT 4th year
> Mob No: 07860896972
> E-mail naveenshukla...@gmail.com <javascript:>
>
--
