382. Linked List Random Node

Leetcode Reservoir Sampling

Given a singly linked list, return a random node's value from the linked list. Each node must have the same probability of being chosen.

Follow up: What if the linked list is extremely large and its length is unknown to you? Could you solve this efficiently without using extra space?

Example:

// Init a singly linked list [1,2,3].
ListNode head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
Solution solution = new Solution(head);

// getRandom() should return either 1, 2, or 3 randomly. 
// Each element should have equal probability of returning.
solution.getRandom();

分析

这道题目比较直接，也是最平常的想法，就是每次调用getRandom()产生一个随机数，随机数的范围在[0, len]之间，其中len是链表的长度。这样就保证了产生的随机数是随机的。

private ListNode head;
private Random random;
private int len;

/** @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;       
    random = new Random();
    for (len = 0; head != null; len++)
        head = head.next;
}

/** Returns a random node's value. */
public int getRandom() {
    int index = random.nextInt(len);
    ListNode cur = this.head;
    for (int i = 0; i < index; i++)
        cur = cur.next;
    return cur.val;
}

但题目里又说了，如果数据量非常大怎么办？上面的解法中有个缺陷，那就是调用一次getRandom()要遍历两遍链表，这在数据量大的时候非常不适合。那么有没有可能只要遍历一次链表就能得到一个随机的链表节点值呢？当然有，水塘抽样算法！

水塘抽样算法，其目的在于从包含$n$个项目的集合S中选取$k$个样本，其中$n$为一很大或未知的数量，尤其适用于不能把所有$n$个项目都存放到主内存的情况。这里是水塘抽样算法的特例，$k=1$。其基本思路如下：

1. 初始化结果为head：result = head.val
2. 初始化 $i = 2$
3. 现在从第二个节点向前依次考虑每个节点
   • 产生0到$i-1$的随机数$j$
   • 如果$j$等于0(或者其他固定的从0到$n-1$的数，将结果取代为现在节点的值
   • $i = i + 1$
   • current = current->next

具体Java代码如下：

private ListNode head;
private Random random;

/** @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;       
    random = new Random();  
}

/** Returns a random node's value. */
public int getRandom() {
    ListNode head = this.head;
    int res = head.val;
    for (int i = 2; head.next != null; i++) {
        head = head.next;
        if(random.nextInt(i) == 0) res = head.val;
    }
    return res;
}