题目
给你一个单链表,随机选择链表的一个节点,并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution
类:
Solution(ListNode head)
使用整数数组初始化对象。int getRandom()
从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
来源:力扣(LeetCode)
解答
直接在初始化时,将链表存储到一个数组中,get时通过随机数选择一个返回即可。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
vector<int> all;
Solution(ListNode *head) {
while (head) {
all.push_back(head->val);
head = head->next;
}
}
int getRandom() {
return all[rand() % all.size()];
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(head);
* int param_1 = obj->getRandom();
*/