[382] Linked List Random Node

微妙的題目（thinking 圖）

取random之前到底要不要下seed 呢？ XD

就，微卡在了奇怪的地方QQ

typedef struct {

int total;

struct ListNode** arr;

} Solution;

Solution* solutionCreate(struct ListNode* head) {

Solution *ret = calloc (1, sizeof(Solution));

(ret->arr) = calloc (10000, sizeof(struct ListNode *));

struct ListNode* ptr = head;

int idx=0;

while (ptr != NULL)

{

ret->arr[idx]= calloc (1, sizeof(struct ListNode));

// ret->arr[idx]->val = ptr->val;

ret->arr[idx]= ptr;

idx++;

ptr = ptr->next;

}

ret->total = idx;

return ret;

}

int solutionGetRandom(Solution* obj) {

// srand(obj->total);

int idx = rand()%(obj->total);

return obj->arr[idx]->val ;

}

void solutionFree(Solution* obj) {

for (int i=0; i<obj->total;i++)

free(obj->arr[i]);

free(obj);

}

寫完之後發現，原來array可以直接存 val 而不用特別去存每個node的pointer

好像也是？！（再度thinking圖）不過行數雖然變少了，但也沒有比較快 XD

typedef struct {

int total;

int arr[10000];

} Solution;

Solution* solutionCreate(struct ListNode* head) {

Solution *ret = calloc (1, sizeof(Solution));

struct ListNode* ptr = head;

int idx=0;

while (ptr != NULL)

{

ret->arr[idx] = ptr->val;

idx++;

ptr = ptr->next;

}

ret->total = idx;

return ret;

}

int solutionGetRandom(Solution* obj) {

int idx = rand()%(obj->total);

return obj->arr[idx] ;

}

void solutionFree(Solution* obj) {

free(obj);

}