Sample a Linked-List Node Uniformly

# Sample a Linked-List Node Uniformly You receive the head of a nonempty singly linked list. Implement: - `Solution(head)`: initialize an object using the supplied list head. - `getRandom() -> int`: choose a node uniformly at random and return its value. If the list has `N` nodes, each node must have probability `1/N` of being selected on each call. Equal values in different nodes remain separate choices. Do not modify node values or `next` links. ### Examples The first list is: ```text head -> [1] -> [2] -> [3] -> null ``` Five calls might return `1, 3, 2, 2, 3`. This is an illustrative random sequence, not a required transcript. Each call returns `1`, `2`, or `3`, each with probability `1/3`; repeated results are allowed. For `head -> [4] -> [4] -> [9] -> null`, each of the three nodes has probability `1/3`. Therefore the returned value is `4` with probability `2/3` and `9` with probability `1/3`. ### Constraints and assumptions - The list contains `1` to `10000` nodes. - Each node value is between `-10000` and `10000`, inclusive. - At most `10000` calls are made to `getRandom`. - Treat the finite list as unchanged during sampling; behavior under external or concurrent list mutation is not specified. - No particular random API or seed is prescribed. State the randomness assumptions used to justify equal probabilities; the reference assumes independent, unbiased integer draws over a requested finite range. ### What a Strong Answer Covers - Equal selection probability for every node, including nodes with duplicate values. - Repeated calls, a one-node list, and preservation of the linked list. - Initialization cost, work per call, and storage requirements. ### Follow-up Questions - What if the list is extremely large and its length is initially unknown? - Can you sample without storing an additional collection proportional to the list length?