#include<bits/stdc++.h>
using namespace std;
struct node
{
    int data;
    node *next;
};
void push(struct node** head, int d)
{
    struct node* t = new node();
    t->next=NULL;
    t->data  = d;
    t->next = (*head);
    (*head)    = t;
}
void selectrandom(node *h)
{
    if(!h)return;
    int ans=h->data;
    for(int i=2;h!=NULL;i++)
    {
    	//change result with probability 1/n
        int v=rand()%i;
        if(v==0)
            ans=h->data;
        h=h->next;
    }
    cout<<ans<<"\t";
}
int main()
{
    node *f=NULL;
    push(&f, 50);
    push(&f, 40);
    push(&f, 30);
    push(&f, 20);
    push(&f, 10);
    for(int i=0;i<50;i++)
        selectrandom(f);
    return 0;
}
 

I2luY2x1ZGU8Yml0cy9zdGRjKysuaD4KdXNpbmcgbmFtZXNwYWNlIHN0ZDsKc3RydWN0IG5vZGUKewogICAgaW50IGRhdGE7CiAgICBub2RlICpuZXh0Owp9Owp2b2lkIHB1c2goc3RydWN0IG5vZGUqKiBoZWFkLCBpbnQgZCkKewogICAgc3RydWN0IG5vZGUqIHQgPSBuZXcgbm9kZSgpOwogICAgdC0+bmV4dD1OVUxMOwogICAgdC0+ZGF0YSAgPSBkOwogICAgdC0+bmV4dCA9ICgqaGVhZCk7CiAgICAoKmhlYWQpICAgID0gdDsKfQp2b2lkIHNlbGVjdHJhbmRvbShub2RlICpoKQp7CiAgICBpZighaClyZXR1cm47CiAgICBpbnQgYW5zPWgtPmRhdGE7CiAgICBmb3IoaW50IGk9MjtoIT1OVUxMO2krKykKICAgIHsKICAgIAkvL2NoYW5nZSByZXN1bHQgd2l0aCBwcm9iYWJpbGl0eSAxL24KICAgICAgICBpbnQgdj1yYW5kKCklaTsKICAgICAgICBpZih2PT0wKQogICAgICAgICAgICBhbnM9aC0+ZGF0YTsKICAgICAgICBoPWgtPm5leHQ7CiAgICB9CiAgICBjb3V0PDxhbnM8PCJcdCI7Cn0KaW50IG1haW4oKQp7CiAgICBub2RlICpmPU5VTEw7CiAgICBwdXNoKCZmLCA1MCk7CiAgICBwdXNoKCZmLCA0MCk7CiAgICBwdXNoKCZmLCAzMCk7CiAgICBwdXNoKCZmLCAyMCk7CiAgICBwdXNoKCZmLCAxMCk7CiAgICBmb3IoaW50IGk9MDtpPDUwO2krKykKICAgICAgICBzZWxlY3RyYW5kb20oZik7CiAgICByZXR1cm4gMDsKfQo=