力扣-382. 链表随机节点

给你一个单链表，随机选择链表的一个节点，并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution 类：
Solution(ListNode head) 使用整数数组初始化对象。
int getRandom() 从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。

class Solution {
vector<int> arr;
public:
    Solution(ListNode* head) {
        while (head) {
            arr.emplace_back(head->val);
            head = head->next;
        }
    }
    
    int getRandom() {
        return arr[rand() % arr.size()];
    }
};

方法：

vector arr;
定义一个数组用来存储节点的值
int getRandom() {

    return arr[rand() % arr.size()];

}
实现随机抽取节点的值
while (head) {

        arr.emplace_back(head->val);
        head = head->next;
    }

把节点对应的值放到arr数组中