# [LeetCode] 382. Linked List Random Node 链表随机节点

2021年09月15日 阅读数：3

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.html

What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?java

Example:node

```// Init a singly linked list [1,2,3].

// getRandom() should return either 1, 2, or 3 randomly. Each element should have equal probability of returning.
solution.getRandom();```

Java:post

```public class Solution {

Random random;

public Solution(ListNode h) {
random = new Random();
}

public int getRandom() {

int r = c.val;
for(int i=1;c.next != null;i++){

c = c.next;
if(random.nextInt(i + 1) == i) r = c.val;
}

return r;
}
}　```

Python:this

```from random import randint

class Solution(object):

"""
@param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node.
"""

# Proof of Reservoir Sampling:
# https://discuss.leetcode.com/topic/53753/brief-explanation-for-reservoir-sampling
def getRandom(self):
"""
Returns a random node's value.
:rtype: int
"""
reservoir = -1
while curr:
reservoir = curr.val if randint(1, n+1) == 1 else reservoir
curr, n = curr.next, n+1
return reservoir
```

C++: 1url

```class Solution {
public:
/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
len = 0;
while (cur) {
++len;
cur = cur->next;
}
}

/** Returns a random node's value. */
int getRandom() {
int t = rand() % len;
while (t) {
--t;
cur = cur->next;
}
return cur->val;
}
private:
int len;
};```

C++: 2spa

```class Solution {
public:
/** @param head The linked list's head. Note that the head is guanranteed to be not null, so it contains at least one node. */
}

/** Returns a random node's value. */
int getRandom() {
int res = head->val, i = 2;
while (cur) {
int j = rand() % i;
if (j == 0) res = cur->val;
++i;
cur = cur->next;
}
return res;
}
private:
};
```

398. Random Pick Index