# Random Linked List Node

# Problem Statement

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 integer array nums.
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 choosen.
```

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`

.

## Linear space complexity solution

A naive solution is to store all nodes in an ArrayList and then randomly pick an item:

```
class Solution:
def __init__(self, head: ListNode):
self.nodes = []
current = head
while current:
self.nodes.append(current.val)
current = current.next
def getRandom(self) -> int:
return random.choice(self.nodes)
```

The `getRandom`

method has `O(1)`

running time. What if the LinkedList is very long? Then `self.nodes`

will consume a lot of memory.

## Constant space complexity solution I

We associate each node with a random number and pick the node associated with the maximum number:

```
class Solution:
def __init__(self, head: ListNode):
self.head = head
def getRandom(self) -> int:
current_max = -1
val = None
current = self.head
while current:
ran = random.random()
if ran > current_max:
current_max = ran
val = current.val
current = current.next
return val
```

## Constant space complexity solution II

Another constant space complexity solution uses Reservoir sampling. It’s a special case with `k = 1`

.

```
class Solution:
def __init__(self, head: ListNode):
self.head = head
def getRandom(self) -> int:
node = self.head
res = None
index = 0
while node:
current = random.randint(0, index)
if current == index:
res = node.val
index += 1
node = node.next
return res
```

One advantange of this solution is it can be easily extended to cases with `k > 1`

. For example, one can be asked to generate 5 random nodes. See a clean implementation here.