Resevior Sampling : https://en.wikipedia.org/wiki/Reservoir_sampling

/** * Definition for singly-linked list. * public class ListNode { *     int val; *     ListNode next; *     ListNode(int x) { val = x; } * } */class Solution {    private ListNode head;    private 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) {        this.head = head;        rand = new Random();    }        /** Returns a random node's value. */    public int getRandom() {        ListNode runner = head.next;        int result = head.val;        for (int i = 1; runner != null; i++, runner = runner.next) {            if (rand.nextInt(i + 1) == i) result = runner.val;        }        return result;    }}/** * Your Solution object will be instantiated and called as such: * Solution obj = new Solution(head); * int param_1 = obj.getRandom(); */