LeetCode – Nodo aleatorio de lista enlazada (Java)

Dada una lista enlazada individualmente, devuelve el valor de un nodo aleatorio de la lista enlazada. Cada nodo debe tener la misma probabilidad de ser elegido.

Hacer un seguimiento:
¿Qué sucede si la lista vinculada es extremadamente grande y no conoce su longitud? ¿Podrías resolver esto de manera eficiente sin usar espacio adicional?

Solución Java

Este problema es trivial, así que me concentro en el problema de seguimiento.

Queremos que la probabilidad de ser elegido sea 1 / cuenta.

Dada una lista 1 -> 2 -> 3 -> 4 -> 5 -> … -> n, la única vez que podemos seleccionar el tercer nodo es cuando el puntero apunta a 3. La probabilidad de seleccionar el tercer nodo es 1/3 * 3/4 ​​* 4/5 * … * (n-1) / n = 1 / n.

public class Solution {
 
    Random r = null;
    ListNode h = null;
 
    public Solution(ListNode head) {
        r = new Random();
        h = head;
    }
 
    /** Returns a random node's value. */
    public int getRandom() {
        int count=1;
        ListNode p = h;
        int result = 0;
        while(p!=null){
            if(r.nextInt(count)==0)
                result= p.val;
            count++;
            p = p.next;
        }
        return result;
    }
}