You are given the head of a singly linked list of unknown length (at least one node). Design Solution so that getRandom() returns the value of a uniformly random node.
new Solution(head, rng) keeps the head and the generator. rng returns numbers in [0, 1)getRandom() walks the list once, with O(1) extra memory (do not copy the values into an array)- For the m-th node (counting from 1), draw once with
Math.floor(rng() * m) and take that node's value if the result is 0. That is one draw per node - The list must be left as it was