https://leetcode.cn/problems/linked-list-random-node/

?

---

這道題我們首先看到題目中的要求：在單鏈表中隨機選取一個鏈表中的結點，要使每個結點被選取的概率是一樣的。

當我們看到隨機這兩個字時，應該就會想起rand()這個函數。接著我們把使用這個函數生成的隨機值與鏈表的長度進行模運算，這樣子求出的結果就不會大于鏈表長度。

//用數組存儲該鏈表
typedef struct {int* arr;int length;
} Solution;Solution* solutionCreate(struct ListNode* head) {Solution* obj = (Solution*)malloc(sizeof(Solution));obj->length = 0;struct ListNode* Node = head;//記錄鏈表長度while(Node){++obj->length;Node = Node->next;}obj->arr = (int*)malloc(sizeof(int) * obj->length);Node = head;//將鏈表節點中的值賦值給數組for(int i =0; i<obj->length;i++){obj->arr[i] = Node->val;Node = Node->next;}return obj;
}int solutionGetRandom(Solution* obj) {//rand生成的隨機值 % 鏈表長度 的值不會大于鏈表長度return obj->arr[rand() % obj->length];
}void solutionFree(Solution* obj) {free(obj->arr);free(obj);
}

?