随机数

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

int getRandom() { int res = head->val; ListNode* node = head->next; int i = 2; while(node){ int j = rand()%i; if(j==0) res = node->val; i++; node = node->next; } return res; } 证：设有n个数，

显然，第n个数的概率为1/n

所以前n-1个数的概率为(n-1)/n

第n-1个数的概率为((n-1)/n) *(1/(n-1)) = 1/n

同理,前n-2个数的概率为(n-2)/n

第n-2个数的概率为((n-2)/n) *(1/(n-2)) = 1/n

。

前2（n-(n-2)）个数的概率为2/n,

第2个数的概率为2/n * 1/2 = 1/n

前1个数的概率为1/n,

所以每个数输出的概率均等为1/n。