# interviewhelp.io

### Grow into top tier organizations

☰ Table of Content

# 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:

 `````` 1 2 3 4 5 6 7 8 9 10 `````` ``````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:

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````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`.

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 `````` ``````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.

Update: 2021-11-19