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 togetRandom
.
Linear space complexity solution
A naive solution is to store all nodes in an ArrayList and then randomly pick an item:


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:


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


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.