力扣382:链表随机结点
给你一个单链表,随机选择链表的一个节点,并返回相应的节点值。每个节点 被选中的概率一样 。
实现 Solution
类:
Solution(ListNode head)
使用整数数组初始化对象。int getRandom()
从链表中随机选择一个节点并返回该节点的值。链表中所有节点被选中的概率相等。
示例:
输入 ["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []] 输出 [null, 1, 3, 2, 2, 3]
思想:统计链表的长度,创建和链表一样大小的数组。将链表中的数据保存到数组中,利用数组的随机存储的特点,随机生成一个结点,然后访问数据即可。
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
typedef struct {
int *data;
int len;
} Solution;
Solution* solutionCreate(struct ListNode* head) {
Solution *s = (Solution*)malloc(sizeof(Solution));
s->len=0;
struct ListNode *p=head;
//统计链表的长度
while(p!=NULL){
p=p->next;
s->len++;
}
//分配链表长度的数组空间
s->data = (int*)malloc(sizeof(int)*s->len);
p=head;
//将链表的值存到数组中
for(int i=0;i<s->len;i++){
s->data[i]=p->val;
p=p->next;
}
return s;
}
int solutionGetRandom(Solution* obj) {
int num = rand()%obj->len;//创建[0,len)的随机数
return obj->data[num];
}
void solutionFree(Solution* obj) {
if(obj->data!=NULL){
free(obj->data);
}
if(obj!=NULL){
free(obj);
}
}
/**
* Your Solution struct will be instantiated and called as such:
* Solution* obj = solutionCreate(head);
* int param_1 = solutionGetRandom(obj);
* solutionFree(obj);
*/
时间复杂度O(n);空间复杂度O(n)