网站策划资料方案_模板网站建设制作_百度网站推广教程_爱站长

382. Linked List Random Node

Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen.

Implement the Solution class:

• Solution(ListNode head) Initializes the object with the head of the singly-linked list head.
• int getRandom() Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be chosen.
   

Example 1:

Input:
[“Solution”, “getRandom”, “getRandom”, “getRandom”, “getRandom”, “getRandom”]
[[[1, 2, 3]], [], [], [], [], []]
Output:
[null, 1, 3, 2, 2, 3]
Explanation:
Solution solution = new Solution([1, 2, 3]);
solution.getRandom(); // return 1
solution.getRandom(); // return 3
solution.getRandom(); // return 2
solution.getRandom(); // return 2
solution.getRandom(); // return 3
// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.

Constraints:

• The number of nodes in the linked list will be in the range $[1,10^4]$.
• $-10^4<=Node.val<=10^4$
• At most $10^4$ calls will be made to getRandom.

From: LeetCode
Link: 382. Linked List Random Node

---

Solution:

Ideas:

1. solutionCreate: Initializes the Solution object, stores the head of the linked list, and seeds the random number generator.

2. solutionGetRandom: Implements reservoir sampling to randomly select a node with equal probability. It iterates over the entire linked list and replaces the current result with a random chance, ensuring each node has an equal chance of being picked.

3. solutionFree: Frees the memory allocated for the Solution object.

Code:

// Definition for singly-linked list.
struct {int val;struct ListNode *next;
}ListNode;typedef struct {struct ListNode* head;
} Solution;Solution* solutionCreate(struct ListNode* head) {Solution* obj = (Solution*) malloc(sizeof(Solution));obj->head = head;srand(time(NULL)); // Initialize random number generatorreturn obj;
}int solutionGetRandom(Solution* obj) {struct ListNode* current = obj->head;int result = current->val;int i = 1;while (current != NULL) {// Pick a random number in range [0, i]if (rand() % i == 0) {result = current->val; // Replace the result with current node's value}current = current->next;i++;}return result;
}void solutionFree(Solution* obj) {free(obj);
}/*** Your Solution struct will be instantiated and called as such:* Solution* obj = solutionCreate(head);* int param_1 = solutionGetRandom(obj);* solutionFree(obj);*/