382_LinkedListRandomNode - a920604a/leetcode GitHub Wiki

class Solution {
private:
    vector<int> vec;
    int size ;
public:
    Solution(ListNode* head) {
        size = 0;
        ListNode *p;
        for(p=head;p;p=p->next) {vec.push_back(p->val);size++;}
    }
    
    int getRandom() {
        
        return vec[rand()%size];
    }
};

class Solution {
private:
    ListNode* head;
public:
    Solution(ListNode* head) {
        this->head = head;
    }
    
    int getRandom() {
        int count = 1;
        ListNode *p = head;
        int ret = 0;
        while(p){
            if(rand()%count==0) ret = p->val;
            
            count++;
            p=p->next;
        }
        return ret;
    }
};