382. Linked List Random Node

https://leetcode.com/problems/linked-list-random-node/description/
Solution 1. Reservoir sampling
class Solution {
    ListNode* head;
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. */
    Solution(ListNode* head) {
        this->head = head;
    }
    /** Returns a random node's value. */
    int getRandom() {
        ListNode* node = head;
        int res = node->val;
        node = node->next;
        int k=1, kpi=2;
        while(node) {
            if(rand()%kpi == 0) res = node->val;
            kpi++;
            node = node->next;
        }
        return res;
    }
};
Solution 2.
class Solution {
    int N;
    int len = 1000;
    ListNode* hd;
    vector<ListNode*> vl;
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. */
    Solution(ListNode* head) {
        hd = head;
        ListNode* p=head;
        N = 0;
        while(p) {
            if(N%len == 0) vl.push_back(p);
            N++;
            p = p->next;
        }
    }
    /** Returns a random node's value. */
    int getRandom() {
        random_device rd;
        uniform_int_distribution<int> dist(0, N-1);
        int n = dist(rd);
        ListNode*p = vl[n/len];
        n = n%len;
        while(n) {
            p = p->next;
            n--;
        }
        return p->val;
    }
};