leetcode 382. 链表随机节点

从头开始计数
第i个点选择的概率是

只需要区[0,i-1]的随机数，如果,取到了0，就更新返回值，否则不更新

class Solution {
public:
    /** @param head The linked list's head.
        Note that the head is guaranteed to be not null, so it contains at least one node. */
    ListNode* head;

    Solution(ListNode* head) {
        this->head = head;
        srand( time(0) );
    }

    /** Returns a random node's value. */
    int getRandom() {
        int cnt = 0;
        int ret = -1;

        ListNode* t = head;
        while( t!=nullptr ){
            cnt ++ ;
            if( rand()%cnt==0 ){
                ret = t->val;
            }
            t = t->next;
        }
        return ret;
    }
};