给定一个单链表,随机选择链表的一个节点,并返回相应的节点值。保证每个节点被选的概率一样。
进阶: 如果链表十分大且长度未知,如何解决这个问题?你能否使用常数级空间复杂度实现?
来源:力扣(LeetCode) 链接:https://leetcode-cn.com/problems/linked-list-random-node 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
class Solution {
vector<int> v;
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) {
while(head)
{
v.push_back(head->val);
head = head->next;
}
}
/** Returns a random node's value. */
int getRandom() {
return v[rand()%v.size()];
}
};
class Solution {
ListNode *H;
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) { H = head; }
/** Returns a random node's value. */
int getRandom() {
int count = 0, i;
ListNode *select, *h = H;
while(h)
{
if(count++ == 0)
select = h;
else
{
i = rand()%count;
if(i < 1)
//0, 概率1/count,每次加入一个节点后,之前选的节点有概率被替换
select = h;
}
h = h->next;
}
return select->val;
}
};