## Algorithm

Problem Name: 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, 104]`.
• `-104 <= Node.val <= 104`
• At most `104` calls will be made to `getRandom`.

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
typedef struct {
int n;
int sz;
struct ListNode *p;
struct ListNode *table[100];  // 100 * 100 indexed list
} Solution;
​
Solution *obj = calloc(1, sizeof(Solution));
//assert(obj);
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);
}
``````
Copy The Code &

Input

cmd
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []]

Output

cmd
[null, 1, 3, 2, 2, 3]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
private:
public:

}

int getRandom() {
int cnt = 1;
while(p){
if(rand() % cnt == 0) res = p;
p = p->next;
cnt++;
}
return res->val;
}
};
``````
Copy The Code &

Input

cmd
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []]

Output

cmd
[null, 1, 3, 2, 2, 3]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {

Random rand;
rand = new Random();
}

public int getRandom() {
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;
}
}
``````
Copy The Code &

Input

cmd
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []]

Output

cmd
[null, 1, 3, 2, 2, 3]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
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);
}
``````
Copy The Code &

Input

cmd
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []]

Output

cmd
[null, 1, 3, 2, 2, 3]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:

self.arr = []

def getRandom(self):
return random.choice(self.arr)
``````
Copy The Code &

Input

cmd
["Solution", "getRandom", "getRandom", "getRandom", "getRandom", "getRandom"] [[[1, 2, 3]], [], [], [], [], []]

Output

cmd
[null, 1, 3, 2, 2, 3]