Algorithm
Problem Name: 382. Linked List Random Node
Problem Link: https://leetcode.com/problems/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 listhead.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, 104]. -104 <= Node.val <= 104- At most
104calls will be made togetRandom.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
typedef struct {
int n;
int sz;
struct ListNode *p;
struct ListNode *head;
struct ListNode *table[100]; // 100 * 100 indexed list
} Solution;
Solution* solutionCreate(struct ListNode* head) {
Solution *obj = calloc(1, sizeof(Solution));
//assert(obj);
obj->p = obj->head = head;
return obj;
}
int solutionGetRandom(Solution* obj) {
unsigned int k, i;
struct ListNode *p;
k = random();
if (!obj->sz) {
while (k != 0 && obj->p) {
if ( obj->n < = 99 * 100 &&
(obj->n % 100) == 0) {
obj->table[obj->n / 100] = obj->p;
}
obj->n ++;
obj->p = obj->p->next;
k --;
}
if (obj->p) {
return obj->p->val;
} else {
obj->sz = obj->n;
}
}
k = k % obj->sz;
if (k < 99 * 100) {
i = k / 100;
p = obj->table[i];
k = k % 100;
} else {
p = obj->table[99];
k -= 99 * 100;
}
while (k != 0) {
p = p->next;
k --;
}
return p->val;
}
void solutionFree(Solution* obj) {
free(obj);
}
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
private:
ListNode* head;
public:
Solution(ListNode* head) {
this->head = head;
}
int getRandom() {
int cnt = 1;
ListNode* p = head, *res;
while(p){
if(rand() % cnt == 0) res = p;
p = p->next;
cnt++;
}
return res->val;
}
};
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
ListNode head;
Random rand;
public Solution(ListNode head) {
this.head = head;
rand = new Random();
}
public int getRandom() {
ListNode curr = head;
int val = curr.val;
for (int i = 1; curr.next != null; i++) {
curr = curr.next;
if (rand.nextInt(i + 1) == i) {
val = curr.val;
}
}
return val;
}
}
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const Solution = function(head) {
this.list = head;
this.arr = [];
loop(head, this.arr);
};
Solution.prototype.getRandom = function() {
const len = this.arr.length;
return this.arr[Math.floor(Math.random() * len)].val;
};
function loop(node, arr) {
if (node == null) return;
arr.push(node);
loop(node.next, arr);
}
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def __init__(self, head):
self.arr = []
while head:
self.arr.append(head.val)
head = head.next
def getRandom(self):
return random.choice(self.arr)
Input
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"]
[[[1, 2, 3]], [], [], [], [], []]
Output
[null, 1, 3, 2, 2, 3]