382. Linked List Random Node

發表於 | 分類於

problem

solution

option 1 - cheat , container to store

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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];
    }
};

option 2 - algo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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;
    }
};