https://leetcode.com/problems/linked-list-random-node/

// Using Reservoir sampling algorithm

// https://discuss.leetcode.com/topic/53812/using-reservoir-sampling-o-1-space-o-n-time-complexity-c/2

/**

 * Definition for singly-linked list.

 * public class ListNode {

 *     int val;

 *     ListNode next;

 *     ListNode(int x) { val = x; }

 * }

 */

public class Solution {

    ListNode h;

    java.util.Random rand;

    /** @param head The linked list's head.

        Note that the head is guaranteed to be not null, so it contains at least one node. */

    public Solution(ListNode head) {

        h = head;

        rand = new java.util.Random();

    }

    /** Returns a random node's value. */

    public int getRandom() {

        if (h == null) {

            return 0;

        }

        int ret = h.val;

        int i = 1;

        ListNode cur = h;

        while (cur.next != null) {

            cur = cur.next;

            i++;

            int f = rand.nextInt() % i;

            if (f == 0) {

                ret = cur.val;

            }

        }

        return ret;

    }

}

/**

 * Your Solution object will be instantiated and called as such:

 * Solution obj = new Solution(head);

 * int param_1 = obj.getRandom();

 */