🌕🌗 382. 链表随机节点

难度: 🌕🌗

问题描述

---

解法

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    // 思路：
    // 蓄水池解法
    // 要想每个节点被选中的概率一样，那么，假设总节点数为 n，每个节点被选中的概率均为 1/n
    // 现在的目标是怎么得到 1/n?
    // 假设最终被选中的节点为 k
    // 我们可以通过 1/k * k/(k + 1) * ... * (n - 1)/n = 1/n 得到
    // 那么怎么解释上式的含义？
    // 1/k 表示在 k 个节点中，某个节点恰好被选中的概率
    // k/(k + 1) 表示在 (k + 1) 个节点中，某个节点不被选中的概率
    // 问：k 前面的节点是否被选中有影响吗？为什么式子从 1/k 开始计算，前面的例如 1/2, 2/3 这些为什么不用考虑？
    // 答：
    // 要保证最终选中的节点为 k，那么说明后面的节点一定不被选中，才能导致最后保留的结果是 k，否则一旦其中某个被选中，结果里面发生替换
    // 而前面的节点无论是否选中，假设前面某个节点 m 被选中，之后 k 被选中是一定的，那么结果会被替换为 k
    // 假设前面某个节点 m 没有被选中，之后 k 被选中，结果仍然会被替换为 k
    // 因此可以看出，概率 1/n 只与 k 及以后的节点有关，前面的无关，因此前面的概率恒为 1
    ListNode head;
    Random r;

    public Solution(ListNode head) {
        this.head = head;
        r = new Random();
    }
    
    public int getRandom() {
        int res = 0;
        ListNode cur = head;
        int count = 1;
        while(cur != null) {
            int tmp = r.nextInt(count); // [0, count) 因此 count == 1 时只能选中 0 这个数
            if(tmp == count - 1) { // 可以选择某个下标作为是否被选中的标准，这里以 [0, count) 的最后一个节点 count - 1 为靶涒
                res = cur.val; 
            }
            count ++;
            cur = cur.next;
        }
        return res;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution obj = new Solution(head);
 * int param_1 = obj.getRandom();
 */

---

输出

---

进阶

1. 如果链表非常大且长度未知，该怎么处理？ 你能否在不使用额外空间的情况下解决此问题？
   • 采用 蓄水池 解法
2. 若链表节点数较少，且频繁调用 随机获取链表节点函数？
   • 在初始化时，将链表节点放入 ArrayList 中，通过随机数快速定位到随机值